Ntarsis 收到了两个整数 $$$n$$$ 和 $$$k$$$ 作为他的生日礼物。他想知道用 $$$n$$$ 作为序列的第 $$$k$$$ 个元素可以形成多少个长度为 $$$k$$$ 的斐波那契序列。
如果对于所有 $$$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 \leq t \leq 2 \cdot 10^5$$$),测试用例的数量。每个测试用例的描述如下。
每个测试用例包含两个整数,$$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$3 \leq k \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例输出一个整数,长度为 $$$k$$$ 的斐波那契类序列的数量,使得序列中的第 $$$k$$$ 个元素为 $$$n$$$。也就是说,输出长度为 $$$k$$$ 的序列 $$$f$$$ 的数量,因此 $$$f$$$ 是一个类似斐波那契的序列,并且 $$$f_k = n$$$。可以证明这个数字是有限的。
示例
输入 #1
8 22 4 3 9 55 11 42069 6 69420 4 69 1434 1 3 1 4
输出 #1
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]$$$ 是唯一的类斐波那契序列。