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