L. Chemistry Exam
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

NCD students can make new inventions, discover new theories, and face big challenges, but they can't pass the chemistry test.

In the last test, all the questions were $$$"True"$$$ or $$$"False"$$$ questions. After the exam, it turned out that all the answers were correct.

Each student represents his exam paper as a decimal number, where each bit is an answer to a question. For example, if Hasan's paper was $$$5$$$, which is ($$$101_2$$$) in binary, this means that he answered the $$$1_{st}$$$ and $$$3_{rd}$$$ questions as $$$"True"$$$, and the rest as $$$"False"$$$, and he got $$$2$$$ marks in the exam.

After the test, all the students went insane because the test was very hard. So they asked you to give them their marks.

Input

The first line contains the number of test cases $$$T$$$.

For each test case, the first line contains integer $$$N$$$ ($$$ 1 \le N \le 10^{5} $$$) the number of students.

The next line contains $$$N$$$ space separated integers $$$A_i$$$ ($$$ 1 \le A_i \le 10^{9} $$$) the mark for each student $$$i$$$.

Output

For each test case print $$$N$$$ integers the number of correct questions each student has answered.

Example
Input
2
5
1 2 3 4 5
4
2 4 8 16
Output
1 1 2 1 2
1 1 1 1