Archiwum zadań programistycznych WWSI

Jak wiadomo dobry informatyk potrzebuje do pracy dobrych warunków. Jacek jest naprawdę dobrym informatykiem jednak warunki w jakich przyszło mu pracować są co najmniej trudne. Jego biurko jest nierówne! Jedna z nóg mebla jest ewidentnie krótsza od pozostałych co sprawia Jackowi niemały kłopot. Monitor stoi krzywo, klawiatura również, na dodatek wiatraczek głośno pracuje.

Wyjście z całej sytuacji jest tylko jedno, trzeba podłożyć coś pod nogę feralnego mebla. Jacek wziął kartkę papieru o szerokości 1 centymetra i długości n centymetrów i zaczął składać ją w następujący sposób: odmierzał x centymetrów od lewej strony i o odmierzone centymetry składał karteczkę w prawo. Biurko będzie stało stabilnie jeżeli po wszystkich złożeniach kartka będzie miała rozmiar 1 na 1 centymetr. Jackowi zależy na czasie, zatem chciałby, aby sposób składania kartki był optymalny (aby musiał składać ją jak najmniej razy).

Wejście

Pierwsza linia wejścia zawiera jedną liczbę naturalną t (1 <= t <= 1000) określającą ilość zestawów danych. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych zawiera dokładnie jedną liczbę naturalną n (1 <= n <= 1000) określająca długość kartki w centymetrach.

Wyjście

Dla każdego zestawu danych należy wypisać w pierwszej linii liczbę z określającą ilość złożeń jakie wykonał Jacek. W drugiej linii zestawu danych należy wypisać z liczb pooddzielanych pojedynczymi spacjami. Liczba i – ta w kolejności oznacza ilość centymetrów jakie Jacek odmierzył przy i – tym złożeniu.

Przykład

Dla danych:

2
11
48

Twój program powinien wypisać:

4
5 3 1 1
6
24 12 6 3 1 1