You are given N positive integer numbers. You need to express the product of these numbers as A*B² where A and B are also integers and A is the smallest possible. Return A modulo 1,000,007.

Input

The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases.

Each test case consists of two lines. In the first line you are given N (1 <= N <= 1000). In the next line you are given N numbers. Each number is between 1 and 100.

Output

For each test case, output the A modulo 1,000,007.

Constraints

Time limit: 3 seconds
Memory limit: 64 megabytes

Examples

input
1
10
2 4 54 8 42 8 7 16 27 14

output
21

Explanation: 2 * 4 * 54 * 8 * 42 * 8 * 7 * 16 * 27 * 14 = 21 * 48384²