Dãy số Fibonacci được Fibonacci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đồ qua 2 bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực.

Henry Dudeney (1857 - 1930) (là một nhà văn và nhà toán học người Anh) nghiên cứu ở bò sữa, cũng đạt kết quả tương tự.

Thế kỉ XIX, nhà toán học Edouard Lucas xuất bản một bộ sách bốn tập với chủ đề toán học giải trí, ông đã dùng tên Fibonacci để gọi dãy số kết quả của bài toán từ cuốn Liber Abaci -- bài toán đã sinh ra dãy Fibonacci.

Trong các buổi học Algorithm ProPTIT thì bài toán Fibonacci đã quá đơn giản với mọi người cho nên \t{Skynet} đã nâng cấp bài toán Fibonacci cho thêm phần thú vị hơn nhưng vẫn rất đơn giản để mọi người "\t{thừa sức làm được!}". Bản nâng cấp đó là Dãy xâu Fibonacci:

Một dãy xâu ký tự \t{G} chỉ bao gồm các chữ cái \t{A} và \t{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 phép cộng \t{(+)} là phép nối hai xâu với nhau.

Bài toán đặt ra là tìm ký tự ở vị trí thứ ~i~ (tính từ ~1~) của xâu Fibonacci thứ ~n~.

Input

• Dòng ~1~ ghi số bộ test.
• Mỗi bộ test ghi trên một dòng 2 số nguyên ~N~ và ~i~ (~1<N<93~). Số ~i~ đảm bảo trong phạm vi của xâu ~G_N~ và không quá ~18~ chữ số.</li>

Output

Ký tự ở vị trí thứ \t{i} (tính từ 1) của xâu Fibonacci thứ \t{n}.

Sample

Input #1

2
6 4
8 19

Output #1

A
B

Problem source: CLB Lập Trình PTIT