FRAKTAL - konkurs programistyczny

Masz do dyspozycji wagę szalkową i odważniki będące potęgami trójki gramów, dla każdej potęgi dokładnie jeden odważnik: 1, 3, 9, 27, 81, ….

Twoim zadaniem jest tak rozmieścić odważniki na szalkach wagi, aby zważyć przedmiot o wadze N gramów, znajdujący się na lewej szalce wagi. Waga szalkowa z ważonym przedmiotem i odważnikami musi być w równowadze.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita T (1 ≤ T ≤ 1000) oznaczająca liczbę przedmiotów do zważenia. W każdym z kolejnych T wierszy znajduje się jedna liczba całkowita N (1 ≤ N ≤ 10¹⁵) oznaczająca masę w gramach przedmiotu znajdującego się na lewej szalce wagi.

Wyjście

Dla każdego ważonego przedmiotu, w osobnym wierszu, należy wypisać dwa ciągi liczbowe rozdzielone znakiem równości. Lewa strona równości musi zawierać najpierw masę przedmiotu podanego na wejściu oraz ewentualne wartości mas odważników znajdujące się na lewej szalce wagi. Prawa strona równości musi zawierać wartości mas odważników znajdujące się na prawej szalce wagi. Wartości odważników na lewej jak i prawej szalce należy wypisać w kolejności rosnącej. Pomiędzy liczbami i znakiem równości należy wstawić pojedynczy znak spacji.

Przykład

4
3
6
10
2024

3 = 3
6 3 = 9
10 = 1 9
2024 1 243 = 81 2187