Square in numbers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Leha is a bright mathematician. Today he is investigating whether an integer is divisible by some square number or not.
He has a positive integer X represented as a product of N integers a_{1}, a_{2}, .... a_{N}. He has somehow figured out that there exists some integer P such that the number X is divisible by P^{2}, but he is not able to find such P himself. Can you find it for him? If there are more than one possible values of P possible, you can print any one of them.
Input
The first line of the input contains an integer T denoting the number of test cases. T test cases follow.
The first line of each test case contains one integer N denoting the number of intgers in presentation of X.
The second line contains N spaceseparated integers a_{1}, a_{2}, .... a_{N}.
Output
For each test case, output a single integer P deoting the answer for this test case. Note that P must be in range from 2 to 10^{18} inclusive. It's guaranteed that at least one answer exists. If there are more than one possible answers, print any.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 100
 1 ≤ a_{i} ≤ 10^{18}
Subtasks
 Subtask 1[19 points]: 1 ≤ a_{1}*a_{2}*...*a_{N} ≤ 10^{6}
 Subtask 2[22 points]: 1 ≤ a_{1}*a_{2}*...*a_{N} ≤ 10^{12}
 Subtask 3[23 points]: 1 ≤ a_{i} ≤ 10^{12}
 Subtask 4[36 points]: no additional constraints
Example
Input: 1 3 21 11 6 Output: 3
Explanation
Example case 1. X = 21 * 11 * 6 = 1386. It's divisible by 9 which is a square number, as 9 = 3^{2}. So P = 3.
Author:  pavel1996 
Tester:  karanaggarwal 
Editorial  http://discuss.codechef.com/problems/SQNUMBF 
Tags  ltime37, medium, numbertheory, pavel1996 
Date Added:  13062016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions