Human experience

Time Limit: 3 Seconds    Memory Limit: 64512 KB

Given n pairs of integers (ai,bi), you should calculate the following equation modulo 109+ 7:

LCM (a1b1, a2b2, ..., anbn)

where LCM is the least common multiple of a set of numbers.

Input

The first line of input contains a single integer t (t ≤ 50), the number of tests that follow. The first line of each test contain an integer n (1 ≤ n ≤ 105), the number of pairs of integers.  The i-th of next n lines contains two integers ai, bi (1 ≤ ai ≤ 106,0 ≤ bi ≤ 109), the base and the power of i-th pair as described in the statement.

Output

For each test you should output a single line, the answer of equation modulo 109+ 7.

Sample Input

2
3
2 4
15 2
6 3
1
2 1000

Sample Output

10800
688423210
Submit

Source: 4th Kashan University's ACM Contest