P4031 [Code+#2] Solvable Problem 2

"What are you doing during the CodePlus contest? Are you free? Can you come solve a Diophantine equation problem?" sublinekelzrip asked qmqmqm. Of course, qmqmqm could not solve a Diophantine equation problem, so sublinekelzrip instead proposed another problem. Now please help qmqmqm solve this one.

The problem is as follows: A sequence $a$ is called a generalized Fibonacci sequence if it satisfies $a_n = a_{n-1} + a_{n-2}$ for $n \ge 3$, and $a_1, a_2$ are arbitrary real numbers. Now please count how many generalized Fibonacci sequences satisfy $a_1 = i$, $a_2$ is an integer in the interval $[l, r]$, and $a_k \bmod p = m$.

Read from standard input. This problem contains multiple test cases. The first line contains a positive integer $T$, the number of test cases. For each test case: One line with six space-separated integers: i, l, r, k, p, m, whose meanings are as defined in the Description.

Write to standard output. Output $T$ lines. Each line contains a single number, the answer for that test case.

 Constraints: For all testdata, $0 \le l \le r$, $1 \le p \le 10^9$, $0 \le m < p$, $T = 10$, $0 \le i \le 10^{18}$, $k \ge 3$. From the CodePlus 2017 December Contest, proudly presented by the Student Association for Algorithms and Programming Competitions, Department of Computer Science and Technology, Tsinghua University. Credit: idea/卢政荣 (Lu Zhengrong), problem setting/卢政荣 (Lu Zhengrong), verification/吕时清 (Lü Shiqing), 茹逸中 (Ru Yizhong), 王聿中 (Wang Yuzhong). Git repo: https://git.thusaac.org/publish/CodePlus201712 We thank Tencent for supporting this contest. Translated by ChatGPT 5