CF1853B.Fibonaccharsis

Ntarsis has received two integers $n$ and $k$ for his birthday. He wonders how many fibonacci-like sequences of length $k$ can be formed with $n$ as the $k$-th element of the sequence.

A sequence of non-decreasing non-negative integers is considered fibonacci-like if $f_i = f_{i-1} + f_{i-2}$ for all $i \gt 2$, where $f_i$ denotes the $i$-th element in the sequence. Note that $f_1$ and $f_2$ can be arbitrary.

For example, sequences such as $[4,5,9,14]$ and $[0,1,1]$ are considered fibonacci-like sequences, while $[0,0,0,1,1]$, $[1, 2, 1, 3]$, and $[-1,-1,-2]$ are not: the first two do not always satisfy $f_i = f_{i-1} + f_{i-2}$, the latter does not satisfy that the elements are non-negative.

Impress Ntarsis by helping him with this task.

Ntarsis 生日收到了两个整数 $n$ 和 $k$。他想知道：有多少个长度为 $k$ 的斐波那契型序列，使得 $n$ 恰好是该序列的第 $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]$ 则不是：前两个序列并非对所有 $i>2$ 都满足 $f_i = f_{i-1} + f_{i-2}$，最后一个序列不满足“所有元素均为非负整数”的条件。

请帮助 Ntarsis 解决这一问题，给他留下深刻印象！

The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^5$), the number of test cases. The description of each test case is as follows.

Each test case contains two integers, $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $3 \leq k \leq 10^9$).

It is guaranteed the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case output an integer, the number of fibonacci-like sequences of length $k$ such that the $k$-th element in the sequence is $n$. That is, output the number of sequences $f$ of length $k$ so $f$ is a fibonacci-like sequence and $f_k = n$. It can be shown this number is finite.

对每个测试用例，输出一个整数，表示长度为 $k$ 且第 $k$ 项为 $n$ 的斐波那契类序列的个数。即，输出满足如下条件的长度为 $k$ 的序列 $f$ 的个数：$f$ 是一个斐波那契类序列，且 $f_k = n$。可以证明该数目是有限的。

There are $4$ valid fibonacci-like sequences for $n = 22$, $k = 4$:

• $[6,8,14,22]$,
• $[4,9,13,22]$,
• $[2,10,12,22]$,
• $[0,11,11,22]$.

For $n = 3$, $k = 9$, it can be shown that there are no fibonacci-like sequences satisfying the given conditions.

For $n = 55$, $k = 11$, $[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]$ is the only fibonacci-like sequence.

对于 $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]$。