#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define ll long long

#define int long long

using namespace std;

const int maxn=, inf=1e9;

int n, a1, l, r, K, p, m, T, mod, x, y;

struct mtx {int mp[][];mtx(){memset(mp, , sizeof(mp));}}base, ans;

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-'&&(f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

mtx operator*(mtx a, mtx b)

{

    mtx c;

    for(int i=;i<;i++)

    for(int j=;j<;j++)

    for(int k=;k<;k++)

    c.mp[i][j]=(c.mp[i][j]+a.mp[i][k]*b.mp[k][j])%p;

    return c;

}

void power(int b)

{

    for(;b;b>>=, base=base*base)

    if(b&) ans=ans*base;

}

int exgcd(int a, int b, int &x, int &y)

{

    if(!b) return x=, y=, a;

    int ans=exgcd(b, a%b, x, y);

    int tmp=x; x=y; y=tmp-a/b*y;

    return ans;

}

inline ll find(int x, int up)

{

    int l=, r=up/p+;

    while(l<r)

    {

        int mid=(l+r)>>;

        if(x+p*mid>=up) r=mid;

        else l=mid+;

    }

    return l;

}

#undef int

int main()

{

    read(T);

    while(T--)

    {

        base.mp[][]=base.mp[][]=base.mp[][]=; base.mp[][]=;

        ans.mp[][]=ans.mp[][]=; ans.mp[][]=ans.mp[][]=;

        read(a1); read(l); read(r); read(K); read(p); read(m); a1%=p;

        power(K-); mod=(m-a1*ans.mp[][]%p+p)%p;

        int d=exgcd(ans.mp[][], p, x, y);

        if(mod%d!=) {puts(""); continue;}

        x=x*(mod/d); p/=d; x=(x%p+p)%p;

        printf("%lld\n", find(x, r+)-find(x, l));

    }

}