13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T5f9,

Kosuke is too lazy. He will not give you any legend, just the task:

Fibonacci numbers are defined as follows:

$$$f(1)=f(2)=1$$$.
$$$f(n)=f(n-1)+f(n-2)$$$ $$$(3\le n)$$$

We denote $$$G(n,k)$$$ as an index of the $$$n$$$-th Fibonacci number that is divisible by $$$k$$$. For given $$$n$$$ and $$$k$$$, compute $$$G(n,k)$$$.

As this number can be too big, output it by modulo $$$10^9+7$$$.

For example: $$$G(3,2)=9$$$ because the $$$3$$$-rd Fibonacci number that is divisible by $$$2$$$ is $$$34$$$. $$$[1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]$$$.

Input

The first line of the input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 10^5$$$).

It is guaranteed that the sum of $$$k$$$ across all test cases does not exceed $$$10^6$$$.

Kosuke's Sloth

Examples