Let’s consider a sequence $\{f(n)\}$ which satisfies following 2 conditions.
1.$f(0) = 0, f(1) = 1$.
2.$f(n)=Af(n-1)+f(n-2)$,for any integer $n > 1$.
Here A is a constant integer.
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)\ mod\ p = x\}|$ , i.e. the number of indices $n$ between $L$ and $R$ such as $f(n)\ mod\ p = x$ .
There are several test cases.
The first line of the input contains an integer $T(1\leq T\leq 120)$ , the number of test cases.
Each of the next $T$ lines contains 5 integers, $A,p,x,L,R(0\leq A < 10^9,2<p<10^9,0\leq x < p,1\leq L\leq R \leq 10^{18})$
Print $T$ lines, containing the answer to the problem.