题目描述

作为滋滋国最具智慧的人，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%）：无特殊限制。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。