310569: CF1853B. Fibonaccharsis

B. Fibonaccharsistime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > 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.

Input

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$.

Output

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.

ExampleInput

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

Note

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.

题目大意：
Ntarsis 收到了两个整数 $ n $ 和 $ k $ 作为他的生日礼物。他想知道有多少个长度为 $ k $ 的斐波那契式序列可以形成，使得 $ n $ 成为序列的第 $ k $ 个元素。

一个非递减非负整数的序列如果满足 $ f_i = f_{i-1} + f_{i-2} $ 对于所有 $ i > 2 $，则被认为是斐波那契式序列。注意 $ 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 $ 的斐波那契式序列的数量。即输出满足 $ f $ 是斐波那契式序列且 $ f_k = n $ 的序列 $ f $ 的数量。可以证明这个数量是有限的。

示例：
输入：
```
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]$ 是唯一的斐波那契式序列。题目大意： Ntarsis 收到了两个整数 $ n $ 和 $ k $ 作为他的生日礼物。他想知道有多少个长度为 $ k $ 的斐波那契式序列可以形成，使得 $ n $ 成为序列的第 $ k $ 个元素。 一个非递减非负整数的序列如果满足 $ f_i = f_{i-1} + f_{i-2} $ 对于所有 $ i > 2 $，则被认为是斐波那契式序列。注意 $ 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 $ 的斐波那契式序列的数量。即输出满足 $ f $ 是斐波那契式序列且 $ f_k = n $ 的序列 $ f $ 的数量。可以证明这个数量是有限的。 示例： 输入： ``` 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]$ 是唯一的斐波那契式序列。