Problem D: Pieces and Bits

Given an even integer N, print a sequence of 2^N different N-bit binary numbers in such way that every element of the sequence (except the first one) has exactly one bit the same as the previous one (e.g. 0001 and 1111)

Input Format

The input starts with an integer T - the number of test cases (T <= 8). T cases follow on each subsequent line, each of them containing the integer N (2 <= N <= 16).

Output Format

For each test case, print a sequence that satisfies the stated condition, one integer per line. Any valid sequence will be accepted.

Sample Input

1
2

Sample Output

0
1
3
2
(The sequence in the sample output in binary is {00,01,11,10})
Jaehyun Park
ACPC 2011