19510번 - Easy Homework 다국어

문제

Let us fix an integer $A$. Consider a sequence $\{f(n)\}$ which satisfies the following two conditions:

1. $f(0) = 0,ドル $f(1) = 1$;
2. $f(n) = A \cdot f(n - 1) + f(n - 2)$ for any integer $n > 1$.

Given a prime $p$ and an integer $x$ (0ドル \leq x \leq p$), your task is to calculate $|\{n : L \leq n \leq R, \ f(n) \bmod p = x\}|,ドル that is, the number of indices $n$ between $L$ and $R$ such that $f(n) \bmod p = x$.

입력

There are one or more test cases.

The first line of input contains an integer $T,ドル the number of test cases (1ドル \leq T \leq 42)$.

Each of the next $T$ lines contains five integers $A,ドル $p,ドル $x,ドル $L$ and $R$ (0ドル \leq A < 10^{9},ドル 2ドル < p < 10^{9},ドル 0ドル \leq x < p,ドル 1ドル \leq L \leq R \leq 10^{18}$). It is guaranteed that $p$ is prime.

출력

Print $T$ lines, one for each test case, containing the answers to the problem.

제한

힌트