Щасливий білет

Пересуваючись громадським транспортом у Кольоровії, наші герої помітили одну особливість – усі білети мали номери, що складалися тільки з нулів та одиниць, а щасливим вважався білет, що не мав у номері трьох підряд розташованих нулів.

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

Вхідні дані

У першому рядку вхідного файлу записана кількість тестів T (1 ≤ T ≤ 10000).

Наступні T рядків містять самі тести. Кожен тест складається з двох цілих чисел — N (1 ≤ N ≤ 50) та K.

Вихідні дані

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

Приклади