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 a1, a2, .... aN. He has somehow figured out that there exists some integer P such that the number X is divisible by P2, 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 space-separated integers a1, a2, .... aN. 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 1018 inclusive. Its guaranteed that at least one answer exists. If there are more than one possible answers, print any. Test Case 1 Input (stdin) 1 3 21 11 6 Expected Output 3 Test Case 2 Input (stdin) 0 Expected Output 0
#include<stdio.h>
#include<math.h>
int main()
{
long long p,t,n,a,i,l,m;
scanf("%lld",&t);
while(t--)
{
p=1;
l=0;
scanf("%lld",&n);
for(i=0;i<n;i++)
{
scanf("%lld",&a);
p*=a;
}
i=2;
m=4;
while(m<=p)
{
if(p%m==0)
{
l=i;
break;
}
i++;
m=pow(i,2);
}
printf("%lld\n",l);
}
return 0;
}