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