WA 40pts 求条

#include<bits/stdc++.h>
using namespace std;
#define debug(i) cout<<"Cute_MKS "<<i<<' '
#define pii pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define int long long
int T,i,l,r,p,mod=114514,m;
struct MTX
{
	int a[3][3];
	MTX operator*(const MTX &x)
	{
		MTX c;
		memset(c.a,0,sizeof(c.a));
		for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) c.a[i][k]=(c.a[i][k]+a[i][j]*x.a[j][k])%mod;
		return c;
	}
}bs;
MTX mtxqp(MTX b,int p)
{
	if(p==1) return b;
	MTX g=mtxqp(b,p>>1);
	if(p&1) return g*g*b;
	else return g*g;
}
void exgcd(int a,int b,int &x,int &y,int &d)
{
	if(b==0){x=1;y=0;d=a;return;}
	exgcd(b,a%b,y,x,d);
	y-=a/b*x;
}
inline void sol()
{
	cin>>i>>l>>r>>p>>mod>>m;
	int f1,f2;
	if(p==1) f1=1,f2=0;
	else if(p==2) f1=0,f2=1;
	else
	{
		MTX fib=mtxqp(bs,p-2);
		f1=fib.a[1][1],f2=fib.a[1][2];
		swap(f1,f2);
	}
	i%=mod;m=((m-i*f1)%mod+mod)%mod;
	int x,y,d;exgcd(f2,mod,x,y,d);
	if(m%d){cout<<"0\n";return;}
	x=(x*(m/d)%(mod/d)+(mod/d))%(mod/d);
	//debug(x)<<'\n';
	int t1=(r-x)/mod,t2=(l-1-x)/mod;
	if(r>=x) t1++;
	if(l-1>=x) t2++;
	cout<<t1-t2<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	bs.a[1][1]=bs.a[1][2]=bs.a[2][1]=1;
	bs.a[2][2]=0;
	cin>>T;
	while(T--) sol();
}