Human experience

Time Limit: 3 Seconds    Memory Limit: 64512 KB

Given n pairs of integers (a_i,b_i), you should calculate the following equation modulo 10⁹+ 7:

LCM (a₁^b₁, a₂^b₂, ..., a_n^b_n)

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 ≤ 10⁵), the number of pairs of integers.  The i-th of next n lines contains two integers a_i, b_i (1 ≤ a_i ≤ 10⁶,0 ≤ b_i ≤ 10⁹), 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 10⁹+ 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