# 2. 题解

$A_2\times Fib_{k-1}=m-G(MOD\ p)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;bool flag=0;dig=0;
while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
if(flag)dig=-dig;
}
LL cur,pre,MOD,T,G,X,Y,t;
void dfs(LL a)
{
if(a==1){pre=0,cur=1;return;}
if(a==2){pre=cur=1;return;}
if(a&1){dfs(a-1),swap(pre,cur),cur=(pre+cur)%MOD;return;}
dfs(a>>1);
LL tem=cur;
cur=(cur*cur%MOD+((cur*pre%MOD)<<1)%MOD)%MOD;
pre=(tem*tem%MOD+pre*pre%MOD)%MOD;
}
LL exgcd(LL a,LL b,LL&x,LL&y)
{
if(!b){x=1,y=0;return a;}
int tmp=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return tmp;
}
int main()
{
IN(T);
begin:while(T--)
{
LL a,l,r,k,m,F1,F2;
IN(a),IN(l),IN(r),IN(k),IN(MOD),IN(m);
if(k==1)
{
if(a%MOD==m)puts("1");
else puts("0");
goto begin;
}
if(k==2)
{
printf("%lld\n",((l-1)/MOD)-(r/MOD));
goto begin;
}
a%=MOD,dfs(k-1),F1=pre,F2=cur;
m=((m-(F1*a)%MOD)%MOD+MOD)%MOD;
G=exgcd(F2,MOD,X,Y);
if(m%G){puts("0");goto begin;}
t=MOD/G,X=((X*m/G)%t+t)%t;
if(X>r){puts("0");goto begin;}
r-=X;
if(X>l)l=0;else l-=X;
printf("%lld\n",((r+t)/t)-((l+t-1)/t));
}
return 0;
}