Read problems statements in Mandarin Chinese and Russian.

This problem's statement is really a short one.

You are given an integer S. Consider an infinite sequence S, 2S, 3S, ... . Find the first number in this sequence that can be represented as Q^{3}, where Q is some positive integer number. As the sought number could be very large, please print modulo (10^{9} + 7).

The number S will be given to you as a product of N positive integer numbers A_{1}, A_{2}, ..., A_{N}, namely S = A_{1} * A_{2} * ... * A_{N}

------ Input ------

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains an integer N.

Then there is a line, containing N space separated integers, denoting the numbers A_{1}, A_{2}, ..., A_{N}.

------ Output ------

For each test case, output a single line containing the first term of the sequence which is the perfect cube, modulo 10^{9}+7.

------ Constraints ------

$1 ≤ T ≤ 10$
$(Subtask 1): N = 1, 1 ≤ S ≤ 10^{9} - 15 points.$
$(Subtask 2): N = 1, 1 ≤ S ≤ 10^{18} - 31 point.$
$(Subtask 3): 1 ≤ N ≤ 100, 1 ≤ A_{i} ≤ 10^{18} - 54 points.$

----- Sample Input 1 ------
2

2

2 2

2

2 3
----- Sample Output 1 ------
8

216
----- explanation 1 ------
Example case 1. First few numbers in the infinite sequence 4, 8, 12, 16, 20, , etc. In this sequence, 8 is the first number which is also a cube (as 23 = 8).
Example case 2. First few numbers in the infinite sequence 6, 12, 18, 24, , etc. In this sequence, 216 is the first number which is also a cube (as 63 = 216).

见题面

见题面