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.

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

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.