题目描述

"As you wish，如你所愿"——艾尼维亚

如果一个单调不降的非负整数序列 $f$，对任意的 $i > 2$，都有 $f_i=f_{i-1}+f_{i-2}$，则该序列被视为 斐波那契类序列 ，其中 $f_i$ 表示序列中的第 $i$ 个元素，请注意，$f_1$ 和 $f_2$ 可以是任意的非负整数。

有多少个长度为 $k$ 的 斐波那契类序列 可以用 $n$ 作为序列的第 $k$ 个元素

例如 $[4,5,9,14]$ 和 $[0,1,1]$ 被认为是 斐波那契类序列 ，而 $[0,0,0,1,1]$ , $[1,2,1,3]$ 和 $[−1,−1,−2]$ 却不是，前两个并不总是满足 $f_i=f_{i-1}+f_{i-2}$ ，后者不满足元素是非负的。

输入格式

第一行包含一个整数 $t( 1≤t≤2⋅10^5）$ ，测试用例的数量。每个测试用例的说明如下。

每个测试用例包含两个整数，$n$ 和 $k(1≤n≤2⋅10^5 ,3≤k≤10^9)$ 。

保证总和 $n$ 在所有测试用例中不超过 $2⋅10^5$ 。

输出格式

对于每个测试样例输出一个整数，代表长度为 $k$ 的 斐波那契类序列 中的第 $k$ 个元素是 $n$ 的个数

样例

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

4
0
1
1052
11571
0
1
0

对于 $n=22$ , $k=4$ 有4种有效的斐波那契类序列:

• $[6,8,14,22]$ ，

• $[4,9,13,22]$ ，

• $[2,10,12,22]$ ，

• $[0,11,11,22]$ 。

对于 $n=3$，$k=9$，可以证明没有满足给定条件的斐波那契类序列。

对于 $n=55$，$k=11$， $[0,1,1,2,3,5,8,13,21,34,55]$ 是唯一类似斐波那契的序列。