B. Fibonaccharsistime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputNtarsis 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.InputThe 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.OutputFor 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
822 43 955 1142069 669420 469 14341 31 4Output
4
0
1
1052
11571
0
1
0
NoteThere 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.
822 43 955 1142069 669420 469 14341 31 4
4 0 1 1052 11571 0 1 0 
['binary search', 'brute force', 'math', '*1200']