B'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 <= q t <= q 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 <= q n <= q 2 cdot 10^5 , 3 <= q k <= q 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. There are 4 valid fibonacci-like sequences for n = 22 , k = 4 : 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. '...