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, ...~ được xây dựng theo quy tắc sau:

• ~f_0 = a~
• ~f_1 = b~
• ~f_n = f_{n - 2} + f_{n - 1}~, với ~n > 1~

Yêu cầu: Cho hai số nguyên dương ~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 tiên chứa số nguyên ~t~ (~1 \le t \le 100~) là số lượng test cần xử lý

~t~ dòng sau mỗi dòng chứa hai số nguyên dương ~n~ và ~k~

OUTPUT

Với mỗi test đưa ra số lượng ký tự a xuất hiện trong ~k~ ký tự đầu tiên của xâu ~f_n~ trên một dòng

SAMPLE INPUT

4
0 1
1 1
3 2
7 7

SAMPLE OUTPUT

1
0
1
3

Giải thích:

• ~f_0 = a~
• ~f_1 = b~
• ~f_2 = ab~
• ~f_3 = bab~