Problem description

Po skończonych studiach, Jaś zatrudnił się w dużej amerykańskiej korporacji produkującej gry wideo i pracuje nad kolejną odsłoną jej bestsellerowej serii. Tradycyjnie, jednym z elementów eksploracji jaskiń, lochów czy zamków były zagadki, które trzeba było rozwiązać, aby przejść dalej. Jaś pracuje nad zaimplementowaniem następującej łamigłówki.

Dany jest ciąg zer i jedynek, w którym gracz może modyfikować cyfry (zamieniać jedynkę na zero i zero na jedynkę) na następujących pozycjach:

• pierwsza pozycja od prawej,
• jedna pozycja na lewo od pierwszej jedynki od prawej.

Na przykład w ciągu 101110100 gracz może zmienić cyfrę ostatnią bądź czwartą od końca. Zagadka jest rozwiązana, gdy gracz otrzyma ciąg składający się tylko z zer.

Biznesowe działy korporacji zdefiniowały wiele wymagań, które gra musi spełniać. Jeden z nich to czas rozgrywki. Potrzeby rynku ciągle się zmieniają, zatem pożądany minimalny czas przejścia gry również. Za każdym razem, gdy to się dzieje, szef Jasia wyznacza liczbę N – minimalną liczbę operacji, którą gracz powinien wykonać, aby rozwiązać zagadkę.

Pomóż Jasiowi i skonstruuj zagadkę, której najszybsze rozwiązanie wymaga dokładnie N operacji, lub stwierdź, że jest to niemożliwe.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita T, oznaczająca liczbę zapytań. Kolejne T wierszy zawiera po jednej liczbie całkowitej N, oznaczającej liczbę operacji, z których musi się składać najkrótsze rozwiązanie zagadki.

Wyjście

Na wyjściu należy wypisać T wierszy, gdzie i-ty z nich powinien zawierać odpowiedź na i-te zapytanie – ciąg zer i jedynek, taki że najkrótszy ciąg operacji, który zamienia go w ciąg samych zer, ma długość N. Jeśli taki ciąg nie istnieje, należy wypisać  − 1.

Wypisany ciąg nie może mieć zer wiodących, tzn. musi zaczynać się od 1 lub być równy 0.

Ograniczenia

1 ≤ T ≤ 100, 0 ≤ N ≤ 10¹⁸.

Przykłady

3
3
5
0

10
111
0