F. Лень Косукэ
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Косукэ слишком ленив. Он не даст вам никакой легенды, только задачу:

Числа Фибоначчи определяются следующим образом:

  • $$$f(1)=f(2)=1$$$.
  • $$$f(n)=f(n-1)+f(n-2)$$$ $$$(3\le n)$$$
Мы обозначаем $$$G(n,k)$$$ как индекс $$$n$$$-го числа Фибоначчи, которое делится на $$$k$$$. Для заданных $$$n$$$ и $$$k$$$ вычислите $$$G(n,k)$$$.

Поскольку это число может быть слишком большим, выведите его по модулю $$$10^9+7$$$.

Например: $$$G(3,2)=9$$$, потому что $$$3$$$-е число Фибоначчи, которое делится на $$$2$$$, равно $$$34$$$. $$$[1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]$$$.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая и единственная строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 10^5$$$).

Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превышает $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число: значение $$$G(n,k)$$$, взятое по модулю $$$10^9+7$$$.

Пример
Входные данные
3
3 2
100 1
1000000000000 1377
Выходные данные
9
100
999244007