Fibonacci Sətirləri

Riyaziyyatda tez-tez rekursiv əlaqələr adlanan üsullar tətbiq olunur. Bu üsullar adətən ədədi ardıcıllıqların təqdimatı üçün istifadə olunur, lakin sıra ardıcıllıqlarının təqdimatı üçün də tətbiq edilə bilər.

Rekursiv əlaqə ilə təqdim olunan ardıcıllıqlardan biri də Fibonaççi ardıcıllığıdır: $F_0=a,F_1=b,...$. Bu ardıcıllıq aşağıdakı kimi təqdim olunur: $F_0=a,F_1=b,F_i=F_{i-2}+F_{i-1}$, $i>1$. İlk yeddi Fibonaççi ardıcıllığı belə görünür: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Dima olimpiada proqramlaşdırma dərnəyində iştirak edir və ardıcıllıqların işlənməsi alqoritmləri ilə maraqlanır. O, yaxınlarda Fibonaççi ardıcıllıqları haqqında məlumat əldə etdi. Tez başa düşdü ki, onların uzunluğu $i$ nömrəsi artdıqca çox sürətlə artır, buna görə də $F_i$ ardıcıllığının bütün simvollarını tapmaq üçün çox böyük yaddaş həcmi tələb olunur. Buna görə də o, bəzi simvolların tapılması məsələsi ilə məhdudlaşmağa qərar verdi.

$k$-cı simvolu $F_i$ ardıcıllığında tapan proqram yazın.

Giriş verilənləri

Birinci sətir testlərin sayını $t$ $(1\le t\le 100)$ ehtiva edir. Növbəti $t$ sətirin hər biri iki tam ədəd $n$ və $k$ $(0\le n\le 45,1\le k\le |F_n|)$, burada $|F_n|$ $F_n$ ardıcıllığının uzunluğunu göstərir, ardıcıllıqdakı simvolların mövqeləri birdən başlayır ehtiva edir.

Çıxış verilənləri

$t$ sətir çıxarın, hər biri müvafiq test üçün yalnız bir simvol ehtiva edir.

Nümunələr