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ⁱ. 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.

Wejście

W pierwszym wierszu zapisano wartość t (t ≤ 250) oznaczającą liczbę haseł. W każdym z następnych t wierszy znajduje się jedna liczba bez zer znaczących oznaczająca hasło do sejfu.

Wyjście

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.

Przykład

Wejście:

2
5
10

Wyjście:

1 2
2 0 1
2 0 2
0