Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS12FACT - O-Factorial

You are given an array of positive integers: A = (A1, A2, .... An).

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 : Ai (1 <= Ai <= 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).


Added by:Tata Dule
Date:2012-12-05
Time limit:0.200s-0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Resource:High School Programming League 2012/13

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.