Easy Homework

Time limit1.5sMemory limit256 MB

Summary

Count the indices n in [L, R] where f(n) mod p equals x, for the sequence f(0)=0, f(1)=1, f(n)=A·f(n-1)+f(n-2).

Level: Hard8 of 10
Topics: Number theory, Matrix, Math
Solved: No attempts yet

Problem

Fix an integer $A$ . A sequence $\{f(n)\}$ satisfies the following two conditions.

$f(0) = 0$ , $f(1) = 1$
$f(n) = A \cdot f(n - 1) + f(n - 2)$ for every integer $n > 1$ .

Given a prime $p$ and an integer $x$ ( $0 \leq x \leq p$ ), count the indices $n$ with $L \leq n \leq R$ that satisfy $f(n) \bmod p = x$ .

Input

The first line 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.

Output

Print $T$ lines. Line $i$ contains the answer for the $i$ -th test case.

Examples1

Example 1
Input
```
2
1 5 0 1 5
2 29 12 3 6
```
Expected output
```
1
2
```