Решите задачу на любом языке, или хотя бы скажите идею как это вообще решать пожалуйста.

На день рождения Ntarsis получил два целых числа n и k . Он задался вопросом, сколько фибоначчи-подобных последовательностей длины k можно сформировать таким образом, чтобы n было k -м элементом последовательности. Последовательность неубывающих неотрицательных целых чисел считается фибоначчи-подобной, если fi=fi−1+fi−2 для всех i>2 , где fi обозначает i -й элемент последовательности. Обратите внимание, что f1 и f2 могут быть произвольными. Например, последовательности [4,5,9,14] и [0,1,1] считаются допустимыми, в то время как [0,0,0,1,1] , [−1,−1,−2] и [1,2,1,3] — нет. Произведите впечатление на Ntarsis, оказав ему помощь в решении этой задачи. Входные данные Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤2⋅105 ) — количество наборов входных данных. Далее следует описание наборов входных данных. Единственная строка каждого набора входных данных содержит два целых числа n и k (1≤n≤2⋅105 , 3≤k≤109 ). Гарантируется, что сумма n по всем наборам входных данных не превышает 2⋅105 . Выходные данные Для каждого набора входных данных выведите одно число — количество допустимых фибоначчи-подобных последовательностей длины k , в которых k -м элементом является n . Иными словами, выведите количество последовательностей f из k элементов таких, что f — фибоначчи-подобная, и fk=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] . Codeforces Round 887 (Div. 2) Соревнование идет 01:51:11 Участник Добавить в избранное → Отослать? Язык: GNU G++20 11.2.0 (64 bit, winlibs) Выберите файл: Файл не выбран Обратите внимание: штраф за попытку, которая не прошла претесты, или за перепосылку составляет 50 баллов (исключения: падение на первом тесте, вердикты "Отказ тестирования" или подобные). Вердикт "Претесты пройдены" не гарантирует, что решение верное и пройдет системное тестирование. → Баллы Балл Задача A 443 Задача B 885 Задача C 1328 Задача D 1770 Задача E 2212 Задача F 2655 Успешный взлом 100 Неудачный взлом -50 Неудачная попытка -50 Перепосылка -50 * Если задача решена с первой попытки на момент 00:36

 for _ in range(int(input())):

  [n, k], cnt = map(int, input().split()), 0

  for p in range(n // 2, n + 1):

    f = [p, n]

    for _ in range(k - 2):

      f[0], f[1] = f[1] - f[0], f[0]

      if f[0] < 0 or f[0] > f[1]: break

    else: cnt += 1

  print(cnt) 

 t = int(input()) 

for _ in range(t): 

    n, k = map(int, input().split()) 

    ans = 0 

    for i in range(n + 1): 

        f = [0] * k 

        f[k - 1] = n 

        f[k - 2] = i 

        ok = True 

        for j in range(k - 3, -1, -1): 

            f[j] = f[j + 2] - f[j + 1] 

            if f[j] < 0 or (j > 0 and f[j] > f[j + 1]): 

                ok = False 

                break 

        if ok: 

            ans += 1 

    print(ans)