B. Фибоначчарсис
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На день рождения Ntarsis получил два целых числа $$$n$$$ и $$$k$$$. Он задался вопросом, сколько фибоначчи-подобных последовательностей длины $$$k$$$ можно сформировать таким образом, чтобы $$$n$$$ было $$$k$$$-м элементом последовательности.

Последовательность неубывающих неотрицательных целых чисел считается фибоначчи-подобной, если $$$f_i = f_{i-1} + f_{i-2}$$$ для всех $$$i > 2$$$, где $$$f_i$$$ обозначает $$$i$$$-й элемент последовательности. Обратите внимание, что $$$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$$$ из $$$k$$$ элементов таких, что $$$f$$$ — фибоначчи-подобная, и $$$f_k = n$$$. Можно показать, что это число конечно.

Пример
Входные данные
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]$$$.