You are given an array ‘ARR’ consisting of ‘N’ positive integers. Your task is to find if the number has exactly 3 factors for each number in the array ‘ARR’.

You have to return an array consisting of ‘0,’ and ‘1’ where ‘0’ means that ‘ARR[index]’ does not have 3 factors and ‘1’ means ‘ARR[index]’ has exactly 3 factors.

For Example:

If ‘N’ = 4 and ‘ARR’ = [3, 5, 4, 2]. 
3 has 2 factors, which are 1 and 3.
5 has 2 factors, which are 1 and 5.
4 has 3 factors, which are  1, 2 and 4.
2 has 2 factors, which are 1 and 2.
Hence, the answer is [0, 0, 1, 0].

Input format :

 The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The next line contains ‘N’ space-separated integers denoting the elements of array ‘ARR’.

Output format :

For each test case, print an array containing 0 and 1 where 1 is present if the number ‘ARR[index]’ has exactly 3 factors. Otherwise, 0 is present.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

 1 <= T <= 10
 1 <= N <= 10^6
 1 < ARR[index] <= 10^12

Time Limit: 1 second