B. Fibonaccharsis
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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.

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