POLSKI SPOJ

Napisz program wyznaczający wszystkie możliwe ciągi binarne o zadanej długości n w kolejności zgodnej z kodem Gray'a. Posłuż się następującą formułą rekurencyjną: Funkcja
gray(int n, int *tab, int k, char direction)
ma wypisać wszystkie ciągi o długości n, dla których k pierwszych liczb jest już ustalone i umieszczone w tablicy tab, (inicjalnie k=0) zgodnie z kolejnością ustaloną przez flagę direction.

• jeśli n=k wypisz wszystkie elementy z tab;
• w pozostałych przypadkach wykonaj funkcje
  gray(n,tab,k+1,1) i gray(n,tab,k+1,0) W zależności od parametru direction wstawiając przed wywołaniem funkcji gray do tablicy tab na pozycji k element 0 a później 1, jeśli direction=1 albo najpierw 1 a później 0, jeśli direction=0

Wejście

W pierwszej linii liczba testów t. W każdym z kolejnych t wierszy znajduje się tylko jedna liczba 0 < n < 12.

Wyjście

Dla każdego testu w oddzielnych liniach wszystkie możliwe ciągi binarne w kolejności zgodnej z kodem gray'a, każdy ciąg w jednej linii. Po każdym przypadku testowym linia odstępu.

Przykład

Wejście:
2
1
4

Wyjście:
0
1

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000