You are given an array of elements \(A_1,\ A_2,\ A_3,\ ...,\ A_N\). If you are considering index \(i\), then you contain a set \(S\) of all elements whose index is not equal to \(i\). Your task is to find out if you can express \(A_i\) as the sum of subsets of \(S\).

For example, you have \(8\) elements such as \(1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8\) and you consider index \(3\). Therefore, set \(S\) is \(\{1,\ 2,\ 4,\ 5,\ 6,\ 7,\ 8 \}\) because you have to exclude the element at index \(i\). The answer is Yes because you select subset \(\{1,\ 2\}\) and its sum is \(3\). Suppose, if you consider index \(8\), then set \(S\) is \(\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7 \}\). The answer is Yes because you can select \(\{1,\ 2,\ 5\}\), \([1,\ 3,\ 4\}\), \(\{2,\ 6\}\), or \(\{3,\ 5\}\).

Similarly, the answer for \(i=2\) is No because set \(S\) is \([1,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8\}\) and there is no possible way such that you can select a subset and have sum \(2\).

Note that you can select no more times than it occurs in set \(S\).

You are given array \(A\). For every index, your task is to determine if it is possible for index \(i\) from \(1\) to \(N\).

Input format

The first line contains \(T\) denoting the number of test cases.
The first line of each test case contains an integer \(N\).
The second line of each test case contains \(N\) space-separated integers \(A_1,\ A_2,\ ...,\ A_N\).

Output format

For each test case, print a single line consisting of \(N\) space-separated integers (0 or 1). Print 0 if it is not possible and 1 if it is possible.

Constraints

\(1 \leq T \leq 1000\)

\(0 \leq A_i\le 1000\) \(\forall i \in [1,N]\)

\(1 \leq N \leq 10000\)

Sum of \(N\) over all test cases does not exceed 10000