Easy Homework

Problem Description

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$ .

Input

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})$

Output

Print $T$ lines, containing the answer to the problem.

Sample Input

2
1 5 0 1 5
2 29 12 3 6

Sample Output

1
2

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9