j06624. 冲刺·斐波那契好数 未做

在研究斐波那契数列的整除性质时，我们把数列中能被 $g$ 整除的项称作「好数」。由于询问量很大，手算已经行不通了，请你编程解决。

定义斐波那契数列：

现有 $t$ 组询问。每组给定两个正整数 $n,g$，请求出满足下面条件的下标 $i$ 的数量：

也就是说，求斐波那契数列前 $n$ 项中，有多少项能被 $g$ 整除。

第一行一个正整数 $t$，表示询问组数。

接下来 $t$ 行，每行两个正整数 $n,g$，表示一组询问。

输出共 $t$ 行，每行一个非负整数，表示前 $n$ 项中能被 $g$ 整除的项数。

【样例解释】

斐波那契数列前 $10$ 项为：$11235813213455$。

• $g=1$：所有项都能被 $1$ 整除，共 $10$ 项；
• $g=2$：第 $3,6,9$ 项能被 $2$ 整除，共 $3$ 项；
• $g=3$：第 $4,8$ 项能被 $3$ 整除，共 $2$ 项；
• $g=4$：第 $6$ 项能被 $4$ 整除，共 $1$ 项；
• $g=5$：第 $5,10$ 项能被 $5$ 整除，共 $2$ 项。

【数据规模与约定】

对于全部测试数据，保证：

• $1\le t\le 10^5$；
• $1\le n\le 10^{18}$；
• $1\le g\le 5\times 10^3$；
• 设所有询问中出现的不同模数构成集合 $S$，则 ${\sum }_{g\in S}g\le 5\times 10^3$。

共 20 个测试点，每个测试点 5 分，合计 100 分。