POLSKI SPOJ

Rozważmy wszystkie ciągi binarne o pewnej długości, które składają się tylko z zer i jedynek, a w których żadne dwie jedynki nie stoją obok siebie. To znaczy, że na przykład ciąg 110 nie jest takim ciągiem długości 3 i nie będziemy go uwzględniać, natomiast ciąg 0101 jest takim ciągiem długości 4.

Napisz program, który znajduje ciąg, który jest K-tym spośród wyżej opisanych ciągów uporządkowanych rosnąco w porządku leksykograficznym.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 500), która określa liczbę zestawów danych. Druga linia składa się z dwóch dodatnich liczb całkowitych N oraz K (0 < N < 44, 0 < K < 1000000000) oznacających odpowiednio długość rozpatrywanych ciągów binarnych oraz miejsce w porządku leksykograficznym poszukiwanego ciągu.

Wyjście

Dla każdego zestawu danych program powinien wypisywać w osobnej linii odnaleziony ciąg albo liczbę −1, jeśli liczba K jest większa niż liczba opisanych ciągów.

Przykład

Wejście:
3
3 1
3 2
3 599

Wyjście:
000
001
-1