Xâu Fibonacci thường được sử dụng để rèn luyện kỹ năng xử lý khi giới thiệu các giải thuật xử lý xâu. Xét dãy xâu ~F_0, F_1, F_2, \dots~ xây dựng theo quy tắc sau:

• ~F_0 = 'a'~
• ~F_1 = 'b'~
• ~F_n = F_{n-2} + F_{n-1}, n > 1~

Yêu cầu: Cho hai số nguyên ~n~ và ~k~ (~0 \le n \le 45~, ~k~ không vượt quá độ dài xâu ~F_n~). Hãy xác định số lượng ký tự ~a~ xuất hiện trong ~k~ ký tự đầu tiên của xâu ~F_n~.

Input

• Dòng đầu ghi số nguyên ~T~ là số test cần xử lý (~1 \le T \le 100~).
• Mỗi dòng trong ~T~ dòng sau ghi hai số ~n~ và ~k~ cách nhau ít nhất một dấu cách.

Output

• Ứng với mỗi test, ghi trên một dòng một số nguyên là kết quả tìm được.

Sample Input 1

4
0 1
1 1
3 2
7 7

Sample Output 1

1
0
1
3