Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Is It a Perfect Square?

Limits 1.5s, 512 MB

Given some numbers, can you tell, if the product of these numbers are a perfect square or not?

A number XX is called perfect square if it can be obtained by multiplying the same number twice. The first few perfect square numbers are 1, 4, 9, 16, 25, 36, 49.

Input

The first line contains an integer TT (0<T1000 < T \le 100), denoting the number of the test case.

Each test case contains an integer NN (1N105 1 \le N \le 10^5), denoting how many numbers to compute. And below that an array AA (1Ai1001 \le A_i \le 100) consisting of NN numbers will be given.

Output

You have to find if the product of the array is a perfect square or not. If the product is a perfect square print YES\texttt{YES} otherwise print NO\texttt{NO}.

Sample

InputOutput
3
1
100
2
5 9
5
1 2 3 4 5
YES
NO
NO

Discussion

Statistics


38% Solution Ratio

NAbdullaEarliest, Apr '19

tanviranindoFastest, 0.1s

NAbdullaLightest, 131 kB

Infinity_IQShortest, 395B

Submit

Login to submit

Editorial

the frequency of prime factors in a perfect square is always even. you can find that if you do some ...

Toph uses cookies. By continuing you agree to our Cookie Policy.