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.