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