Jak wiesz, bierzesz udział w Chińskim Konkursie Zadań Konstrukcyjnych (Chinese Constructive Problem Contest, CCPC) i bez wątpienia uczelnia przygotowująca zadania — Uniwersytet Sun Jat-sena, jako Królestwo Konstrukcji — bardzo pragnie, abyś zmierzył się z kilkoma powiązanymi problemami.

Mały U jest studentem w Królestwie Konstrukcji. Na zajęciach z algorytmiki Mały U poznał problem MCOP (Matrix Chain Ordering Problem — problem nawiasowania iloczynu macierzy). Oto wprowadzenie do MCOP:

Na wejściu algorytmu dany jest ciąg dodatnich liczb całkowitych o długości $n \ge 3$, $[w_1, w_2, \dots, w_n]$. Poniższy wzór mnoży $n - 1$ macierzy, aby ostatecznie otrzymać nową macierz:

$$M = M_1 \times M_2 \times \cdots \times M_{n-1}$$

gdzie $M_i$ jest macierzą o wymiarach $w_i \times w_{i+1}$. Mnożenie macierzy jest łączne, więc zmiana kolejności mnożenia da tę samą macierz końcową $M$, jednak liczba operacji może się różnić. Celem problemu jest znalezienie optymalnej strategii mnożenia spośród $(n - 2)!$ możliwych strategii, tak aby łączna liczba operacji wymaganych do pomnożenia macierzy była jak najmniejsza. Zakładamy tutaj, że pomnożenie macierzy o wymiarach $p \times q$ oraz $q \times r$ daje macierz o wymiarach $p \times r$ i wymaga $pqr$ operacji. Minimalną łączną liczbę operacji potrzebnych do obliczenia $M$ przy optymalnej strategii oznaczamy jako $\text{MCOP}([w_1, w_2, \dots, w_n])$.

Mały U nauczył się na zajęciach, jak rozwiązać ten problem w wystarczająco dobrej złożoności czasowej, ale jako student Królestwa Konstrukcji naturalnie pomyślał o następującym zadaniu:

Dana jest liczba całkowita $X$, spełniająca $1 \le X \le 10^9$. Musisz skonstruować ciąg liczb całkowitych o długości $l$, $[a_1, a_2, \dots, a_l]$, spełniający następujące wymagania:

• $3 \le l \le 6$;
• Dla każdego $i \in [1, l]$ zachodzi $1 \le a_i \le 4000$;
• $\text{MCOP}([a_1, a_2, \dots, a_l]) = X$.

Mały U zaimplementował już sprawdzarkę (checker) przy użyciu algorytmu poznanego na zajęciach, a Twoim zadaniem jest rozwiązanie tego problemu konstrukcyjnego.

Wejście

To zadanie zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 500$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego wejście składa się z pojedynczego wiersza zawierającego liczbę całkowitą $X$ ($1 \le X \le 10^9$), której znaczenie podano w treści zadania.

Wyjście

Dla każdego przypadku testowego: najpierw wypisz wiersz z liczbą całkowitą $l$ ($3 \le l \le 6$), oznaczającą długość skonstruowanego ciągu. Następnie wypisz wiersz z $l$ liczbami całkowitymi, reprezentującymi skonstruowany ciąg.

Można udowodnić, że dla każdego wejścia $X$ zawsze istnieje konstrukcja spełniająca wymagania. Jeśli istnieje wiele takich konstrukcji, wypisz dowolną z nich.

Przykład

Przykładowe wejście 1

2
90
10

Przykładowe wyjście 1

4
5 3 2 6
3
1 1 10

Uwaga

Dla pierwszego przypadku testowego skonstruowany ciąg to $[5, 3, 2, 6]$, co oznacza konieczność wykonania łańcuchowego mnożenia trzech macierzy o wymiarach $5 \times 3$, $3 \times 2$ oraz $2 \times 6$. Rozważmy dwie strategie mnożenia:

• Najpierw pomnóż $M_1$ i $M_2$, aby otrzymać macierz o wymiarach $5 \times 2$, a następnie pomnóż przez $M_3$, co odpowiada wyrażeniu $(M_1 \times M_2) \times M_3$. Łączna liczba operacji wynosi wówczas $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$;
• Najpierw pomnóż $M_2$ i $M_3$, aby otrzymać macierz o wymiarach $3 \times 6$, a następnie pomnóż przez $M_1$, co odpowiada wyrażeniu $M_1 \times (M_2 \times M_3)$. Łączna liczba operacji wynosi wówczas $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$.

Tutaj celem jest zminimalizowanie łącznej liczby operacji, zatem $\text{MCOP}([5, 3, 2, 6]) = \min(90, 126) = 90$.