Счастливый билет

Передвигаясь общественным транспортом по Цветочной, наши герои заметили одну особенность – все билеты имели номера, состоявшие только с нулей и единиц, а счастливым считался билет, не имевший в номере трёх подряд расположенных нулей.

Пана Коцкого заинтересовал вопрос – если номер билета имеет N цифр, то каким будет номер К-го счастливого билета?

Входные данные

В первой строке входного файла записано количество тестов T (1 ≤ T ≤ 10000).

Последующие T строк содержат сами тесты. Каждый тест состоит из двух целых чисел — N (1 ≤ N ≤ 50) и K.

Выходные данные

Для каждого теста выведите K-тую в лексикографическом порядке счастливую последовательность длины N. Гарантируется, что количество счастливых последовательностей не менее K.

Примеры