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