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≤x≤p) , your task is to calculate |{n|L≤n≤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≤T≤120) , the number of test cases.
Each of the next T lines contains 5 integers, A,p,x,L,R(0≤A<109,2<p<109,0≤x<p,1≤L≤R≤1018)
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
