### 问题描述 作为无限刻印的拥有者，梅比乌斯博士最近突然对斐波那契数列充满了兴趣。她想要知道，在前 $n$ 个斐波那契数中，是 $m$ 的倍数的有多少个。斐波那契数列： $$ F_1=1 \\ F_2=1 \\ F_n=F_{n-1}+F_{n-2}(n\geq 3) $$ ### 输入格式 输入第 $1$ 行包含一个正整数 $T$，表示测试数据的组数。 每组测试数据包含两个正整数 $n$ 和 $m$。 ### 输出格式 输出一行，这一行只包含一个整数，表示答案。 ### 样例输入 ```text 1 4 3 ``` ### 样例输出 ```text 1 ``` ### **说明/提示** 对于所有评测数据，$1\leq T\leq 10^6，1\leq n\leq 10^{18}，2\leq m\leq 10^4$。 样例中，$\{1,1,2,3\}$ 中，是 $3$ 的倍数的只有 $1$ 个，因此答案 $=1$。