“codeplus比赛的时候在做什么？有没有空？能来解决丢番图方程问题吗？”sublinekelzrip这样问qmqmqm。
当然，qmqmqm并不会丢番图方程问题，所以sublinekelzrip改为提出了另一个题目，现在请你帮助qmqmqm解决这个题目。
这个问题是这样的：
若一个数列aaa满足条件an=an−1+an−2,n≥3a_n=a_{n-1}+a_{n-2},n \geq 3an=an−1+an−2,n≥3,而a1,a2a_1,a_2a1,a2为任意实数，则我们称这个数列为广义斐波那契数列。
现在请你求出满足条件a1=ia_1=ia1=i，a2a_2a2为区间[l,r][l,r][l,r]中的整数，且akmodp=m的广义斐波那契数列有多少个。
从标准输入读入数据。
本题包含多组数据，输入第一行包含一个正整数TTT，表示数据组数。对于每组数据：
一行六个用空格隔开的整数i,l,r,k,p,mi,l,r,k,p,mi,l,r,k,p,m，意义如「题目描述」所示。
输出到标准输出。
输出共TTT行，每行一个数表示该组数据的答案。
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
3 1 4 1 5 9
对于所有数据，0≤l≤r0 \leq l \leq r0≤l≤r,1≤p≤1091 \leq p \leq 10^91≤p≤109,0≤m<p0 \leq m < p0≤m<p,T=10T=10T=10,0≤i≤10180 \leq i \leq 10^{18}0≤i≤1018,k≥3k \geq 3k≥3。
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。Credit：idea/卢政荣 命题/卢政荣 验题/吕时清，茹逸中，王聿中Git Repo：https://git.thusaac.org/publish/CodePlus201712感谢腾讯公司对此次比赛的支持。