A Big Integer

Problem Description

You are given a very large integer $x$, which can be written as $x = \prod_{i = 1}^{n} p_i^{c_i}$, where $p_i$ is a prime. How many pairs of coprime factors of $x$ are there?

Input Format

The first line gives an integer $T$ ($1 \le T \le 10^2$), the number of test cases.

For each test case, the first line gives an integer $n$ ($1 \le n \le 10^4$).

The following $n$ lines each give two integers $p_i$ and $c_i$, with $1 \le p_i, c_i \le 10^9$. It is guaranteed that each $p_i$ is a prime and that they are pairwise distinct.

Output Format

Output $T$ lines, each containing one integer: the answer for that test case. The answer may be very large, so output it modulo $10^9 + 7$.

Sample Input

1
2
2 2
3 1

Sample Output

15

Sample Explanation

$x = 12$, whose factors are $1, 2, 3, 4, 6, 12$.

The coprime factor pairs are:

$(1, 1), (1, 2), (1, 3), (1, 4), (1, 6)$

$(1, 12), (2, 1), (2, 3), (3, 1), (3, 2)$

$(3, 4), (4, 1), (4, 3), (6, 1), (12, 1)$

for a total of $15$ pairs.