Renomowana firma jubilerska zamówiła u Ciebie oprogramowanie zabezpieczające sejfy. Firma produkuje dwa rodzaje sejfów do przechowywania diamentów - jeden z $20$ przełącznikami, a drugi z $200$ przełącznikami. Aby otworzyć sejf potrzebujesz hasła, które składa się z ciągu cyfr. Opracuj program, który na podstawie hasła wygeneruje sposób ustawienia przełączników. Przełączniki ponumerowano od $0$ do $N-1$, $i$-tej pozycji przyporządkowano wartość $3^i$. Pojedynczy przełącznik ma 3 stany (Góra, Zero i Dół). Sejf otwiera się jeżeli suma wartości przyporządkowanych przełącznikom ustawionym do góry odjąć suma wartości przyporządkowanych przełącznikom ustawionym na dół równa się wartości hasła.</p>

Opracuj program, który:

• wczyta ze standardowego wejścia hasła do sejfów
• dla każdego hasła wygeneruje ustawienie przełączników,
• wypisze wynik na standardowe wyjście.

W pierwszym wierszu zapisano wartość $N$ oznaczającą liczbę haseł ($1 ≤ N ≤ 250$). W każdym z następnych $N$ wierszy znajduje się jedna liczba bez zer znaczących oznaczająca hasło do sejfu. Połowa testów zawiera wyłącznie hasła odpowiadające sejfom z $20$ przełącznikami.

출력 형식

Dla każdego hasła wypisz stan przełączników otwierających sejf w dwóch wierszach. W pierwszym wierszu wypisz liczbę przełączników ustawionych do góry oraz ich numery, w drugim wierszu liczbę przełączników ustawionych w dół oraz ich numery. Wszystkie liczby w obrębie jednego wiersza należy oddzielać pojedynczym znakiem spacji.

예제 입력

2
5
10

예제 출력

1 2
2 0 1
2 0 2
0