【题目描述】
作为滋滋国最具智慧的人，Lyra寻找出了日食的规律，自世界诞生之日起，第$i$天有一个特征值$S_i$，满足如下方程：
$S_1=A$；
$S_2=B$；
$S_i=(XS_{i-1}+YS_{i-2}+Z) bmod P;（i≥3）$
Lyra发现，如果有一天满足$S_i=C$，则那一天就会发生日食，现在Lyra想知道，从第$L$天到第$R$天中有多少天会发生日食。
【输入】
第一行输入一个整数T表示数据组数。
对于每组数据输入一行八个整数$A,B,X,Y,Z,P,C,Q$。$A,B,X,Y,Z,P,C$意义如题意所述,$Q$表示$L,R$询问的组数。
接下来$Q$行，每行两个正整数$L,R$，表示一组询问。
【输出】
对于每组询问输出一行一个整数，表示$[L,R]$区间中有多少个$i$满足$S_i=C$。
【输入样例】
2 1 1 1 1 1 3 1 6 1 2 2 3 3 4 4 5 5 6 6 7 1 2 3 4 5 19 2 4 2 6 23 66 233 666 2333 6666
【输出样例】
2 1 0 0 0 1 1 4 48 482
【提示】
【数据规模】
对于所有的数据，$T≤2，1≤Q≤2×10^4，1≤L≤R≤10^{18}，0≤A,B,X,Y,Z,C<P≤10007$且$P$是质数。
子任务1（15%）：$R≤10^7$。
子任务2（15%）：$P≤1000$。
子任务3（25%）：$Q=1$。
子任务4（45%）：无特殊限制。