Рядки Фібоначчі
У математиці досить часто застосовуються так звані рекурентні співвідношення. Як правило вони застосовуються для подання числових послідовностей, але можуть застосовуватись і для подання послідовностей рядків.
Одним з прикладів рядків, які подаються рекурентним співвідношенням є рядки Фібоначчі F_0=a, F_1=b, ... . Вони подаються наступним чином: F_0=a, F_1=b, F_i=F_{i-2}F_{i-1}, i > 1. Перші сім рядків Фібоначчі мають наступний вигляд: a, b, ab, bab, abbab, bababbab, abbabbababbab.
Діма займається у гуртку олімпіадного програмування і цікавиться алгоритмами опрацювання рядків. Нещодавно він взнал про рядки Фібоначчі. Він швидко зрозумів, що їх довжина зі збільшенням номеру i росте дуже швидко, тому задача знаходження усіх символів рядка F_i потребує занадто великого об'єму пам'яті. Саме тому він вирішив обмежитись задачею знаходження деяких символів.
Напишіть програму, яка знаходить k-ий символ рядка F_i.
Вхідні дані
Перший рядок містить кількість тестів t (1 ≤ t ≤ 100). Кожен з наступних t рядків містить два цілих числа n і k (0 ≤ n ≤ 45, 1 ≤ k ≤ |F_n|, через |F_n| позначено довжину рядка F_n, позиції символів у рядку нумеруються з одиниці).
Вихідні дані
Виведіть t рядків, кожен з яких містить рівно один символ — відповідь для відповідного тесту.