SP25867 DIVFIBS - Divisible Fibonacci Numbers

在数学中，斐波那契数列的每一项是前两项之和。它的前几项为： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 假如从下标 1 开始，该数列的第 6 项是 8，8 可以被 1, 2, 4 和 8 整除。现在给定数列中的两个下标 $L$ 和 $R$（其中 $L \leq R$），你需要确定在下标从 $L$ 到 $R$ 的这些斐波那契数中，有多少个是 $M$ 的倍数。

输入的第一行是一个整数 $T(1 \leq T \leq 500)$，表示总共有 $T$ 个测试用例。接下来有 $T$ 行，每行包括三个整数 $L, R (1 \leq L \leq R \leq 100000)$ 和 $M (1 \leq M \leq 10^{18})$。

对于每个测试用例，输出一行，表示在指定范围内能被 $M$ 整除的斐波那契数的个数。 **本翻译由 AI 自动生成**