# 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^{9}+ 7:

LCM (a_{1}^{b1}, a_{2}^{b2}, ..., a_{n}^{bn})

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^{5}), the number of pairs of integers. The i-th of next n lines contains two integers a_{i}, b_{i }(1 ≤ a_{i }≤ 10^{6},0 ≤ b_{i }≤ 10^{9}), 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^{9}+ 7.

## Sample Input

2 3 2 4 15 2 6 3 1 2 1000

## Sample Output

10800 688423210Submit

Source: 4th Kashan University's ACM Contest