Một dãy xâu ký tự ~G~ chỉ bao gồm các chữ cái A và B được gọi là dãy xâu Fibonacci nếu thỏa mãn tính chất: ~G(1) = A~; ~G(2) = B~; ~G(n) = G(n-2) + G(n-1)~ với ~n \ge 3~. Trong đó, phép cộng (+) là phép nối hai xâu với nhau.

Yêu cầu: Tìm ký tự ở vị trí thứ ~i~ (vị trí đánh số từ 1) của xâu Fibonacci thứ ~N~.

Input

• Dòng đầu tiên gồm 1 số nguyên ~T~ ~(T \le 100)~.
• ~T~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~N~ và ~i~ ~(0 < N < 93)~ và ~(1 \le i \le 10^{18})~.

Output

• Ứng với mỗi dòng test case, in ra đáp án của bài toán.

Sample Input 1

2
6 4
8 19

Sample Output 1

A
B