题号：NC14825
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
若一个数列a满足条件an=an-1+an-2,n ≥ 3,而a1,a2为任意实数，则我们称这个数列为广义斐波那契数列。
现在请你求出满足条件a1=i，a2为区间[l,r]中的整数，且ak mod p=m的广义斐波那契数列有多少个。
输入描述:
本题包含多组数据，输入第一行包含一个正整数T，表示数据组数。对于每组数据：
一行六个用空格隔开的整数i,l,r,k,p,m，意义如题目描述所示。
输出描述:
输出共T行，每行一个数表示该组数据的答案。
示例1
输入
复制
6
2 17 68 3 23 1
1 17 68 3 57 1
5 17 68 10 11 9
5 17 68 10 71 9
10 17 68 11 12 3
10 17 68 8 6 4
备注:
对于所有数据，0 ≤ l ≤ r,1 ≤ p ≤ 109,0 ≤ m < p,T=10,0 ≤ i ≤ 1018,k ≥ 3。