You are given an integer array A consisting of N elements. Your task is to determine for every element if any of its powers can be expressed as the sum of any subset of array A.
Let S be any subset of A.
S.size()∑i=1Si=A[i]K where K≥2.
See sample for a better explanation.
If it is possible to do for any element, print 1. Otherwise, print 0.
Input format
- The first line contains T denoting the number of test cases.
- The first line of each test case contains an integer N denoting the number of elements in array A.
- The second line of each test case contains N space-separated integers of array A.
Output format
For each test case, print a single line of N space-separated integers (0/1). Print 0 if there is no subset such that the sum of that subset is equal to any power greater than 1 of the element at this index. Otherwise, print 1.
Constraints
1≤T≤5
1≤N≤100
1≤A[i]≤100∀i∈[1,N]
Let us consider answers for each index:
1st index: If we choose subset {1} of the array we know 12 =1 so answer for this index is 1 because element at this index 1 can be expressed. Note that we could also choose higher power.
2nd index: If we choose subset {3,5} of the array we know 23 =8 so answer for this index is 1.
Note that we could also choose power 2 and have set {4} or {1,3}.
3rd index: If we choose subset {1,8} of the array we know 32 =9 so answer for this index is 1.
8th index: There is no subset of array which equals 82,83 or higher powers so answer for this case is 0.
