Передвигаясь общественным транспортом по Цветочной, наши герои заметили одну особенность – все билеты имели номера, состоявшие только с нулей и единиц, а счастливым считался билет, не имевший в номере трёх подряд расположенных нулей.
Пана Коцкого заинтересовал вопрос – если номер билета имеет N цифр, то каким будет номер К-го счастливого билета?
В первой строке входного файла записано количество тестов T (1 ≤ T ≤ 10000).
Последующие T строк содержат сами тесты. Каждый тест состоит из двух целых чисел — N (1 ≤ N ≤ 50) и K.
Для каждого теста выведите K-тую в лексикографическом порядке счастливую последовательность длины N. Гарантируется, что количество счастливых последовательностей не менее K.