High School Programming League Problems Archive

You are given an array of positive integers: A = (A₁, A₂, .... A_n).

Your task is to find the maximum possible X such that the product of all numbers from A is equal to X! * Y, for some positive integer Y.

Input

In the first line you are given the number of test cases T (T <= 10).

Next, T pairs of lines follow. In the first line of each pair there is an integer N (1 <= N <= 100000) - the number of integers in A. In the second line you are given the elements of A : A_i (1 <= A_i <= 100000).

Output

For every test case, in a separate line, print the maximum possible X.

Example

Input:
3
5
1 2 6 60 56
6
11 19 43 6 13 25
1
24

Output:
8
3
4

Explanation

Test 1 : The product of all numbers is 40320 or 8! * 1, so the answer is 8.
Test 2 : The product of all numbers is 17524650 or 3! *  2920775  so the answer is 3.
Test 3 : 24 or 4!*1 so the answer is 4.

Scoring

By solving this problem you score 10 points. Your code will be tested on 5 test sets (2 points for every correctly solved test set).