CF1853B Fibonaccharsis

Ntarsis 在他的生日的时候收到了两个整数 $n$ 和 $k$ 。他想知道有多少个长度为 $k$ 的斐波那契序列可以用 $n$ 作为序列的第 $k$ 个元素。 如果一个单调不降的非负整数序列 $f$，对任意的 $i > 2$，都有 $f_i=f_{i-1}+f_{i-2}$，则该序列被视为斐波那契类序列，其中 $f_i$ 表示序列中的第 $i$ 个元素。请注意，$f_1$ 和 $f_2$ 可以是任意的非负整数。 例如 $[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}$ ，后者不满足元素是非负的。 通过帮助 Ntarsis 完成这项任务来打动他。

第一行包含一个整数 $t( 1≤t≤2⋅10^5）$ ，测试用例的数量。每个测试用例的说明如下。 每个测试用例包含两个整数，n和 $k(1≤n≤2⋅10^5 ,3≤K≤10^9)$ 。 保证总和 $n$ 在所有测试用例中不超过 $2⋅10^5$ 。

对于每个测试样例输出一个整数，长度为 $k$ 的斐波那契类序列中的第 $k$ 个元素是 $n$ 。即输出长度为 $f$ 的序列数 $k$ ，所以 $f$ 是一个斐波那契类序列，并且 $f_k=n$ 。可以证明这个数字是有限的。

对于 $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]$ 是唯一类似斐波那契的序列。