Công thức lặp có thể gặp với cả biểu thức xâu. Biểu thức xâu Fibonacci được xác định bằng bằng công thức lặp F₀ = a, F₁ = b, F₂ = F₀+F₁, . . .F_n=F_n-2+F_n-1, . . . Các xâu đầu tiên xác định theo công thức lặp này là a, b, ab, bab, abbab, bababbab, abbabbababbab, . . .

Độ dài của xâu tăng lên rất nhanh. Vì vậy ta chỉ xét bài toán xác định một ký tự của một xâu trong dãy các xâu này.

Yêu cầu: Cho 2 số nguyên n và k. Hãy xác định ký tự thứ k của xâu F_n. Các ký tự trong F_n được đánh số bắt đầu từ 1.

INPUT:

• Dòng đầu tiên chứa số nguyên T – số bộ dữ liệu test (1 ≤ T ≤ 100),
• Mỗi dòng trong T dòng sau chứa 2 số nguyên n và k (0 ≤ n ≤ 45, 1 ≤ k ≤ length(F_n).

OUTPUT:

• Kết quả mỗi test đưa ra trên một dòng dưới dạng một ký tự.