Dãy Fibonacci kiểu mới là 1 dãy không giảm những số nguyên không âm có dạng \(f_i = f_{i-1} + f_{i-2}\) với tất cả \(i \gt 2\) và \(f_i\) thể hiện phần tử thứ \(i\) trong dãy. Lưu ý: \(f_1\) và \(f_2\) là tùy ý.

Ví dụ: Dãy [4,5,9,14] là dãy Fibonacci kiểu mới.

Tính xem có bao nhiêu dãy Fibonacci kiểu mới có chiều dài \(k\) có thể được tạo thành với \(n\) là phần tử thứ \(k\) của dãy.

Dữ liệu vào:

• Dòng thứ nhất: số lượng bộ test \(t\) (\(1 \le t \le 2.10^5\))
• \(t\) dòng tiếp theo: mỗi dòng là 1 bộ test bao gồm 2 số nguyên \(n\) và \(k\) với (\(1 \le n \le 2.10^5\) và \(3 \le k \le 10^9\))

Dữ liệu ra:

Với mỗi bộ test, output trên 1 dòng số lượng dãy Fibonacci kiểu mới thỏa yêu cầu.

Input

8
22 4
3 9
55 11
42069 6
69420 4
69 1434
1 3
1 4

Output

4
0
1
1052
11571
0
1
0

Giải thích

Test 1: Với n=22, k=4 có 4 dãy Fibonacci kiểu mới có chiều dài là 4 và phần tử thứ 4 là 22 là [6,8,14,22],[4,9,13,22],[2,10,12,22],[0,11,11,22].
Test 2: Với n=3, k=9 không có dãy Fibonacci kiểu mới nào thỏa yêu cầu.