CF2033F.Kosuke's Sloth

Kosuke 太懒了。他不会给你任何背景，只给你任务：

斐波那契数列定义如下：

• $f(1)=f(2)=1$。
• $f(n)=f(n-1)+f(n-2)$，其中 $n \ge 3$。

我们用 $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$ 取模的结果。

由 ChatGPT 4.1 翻译