#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=100000,MOD=59964251,phi=59870352;

int te,ans;char s[maxn+5];
int m,D,K,sum[maxm+5];LL yu;bool fl;
int u[maxm+5],p[maxm+5];bool pri[maxm+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) {p[++p[0]]=i;u[i]=-1;}
        for (int j=1,t;j<=p[0] && (t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) {u[t]=0;break;} else u[t]=-u[i];}
    }
    u[1]=1;for (int i=2;i<=n;i++) u[i]=(u[i]+MOD)%MOD;
}
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
int Count(int A){
    if (gcd(A,MOD)==1) return Pow(A,yu);
    else return Pow(A,fl?yu+phi:yu);
}
int main(){
    Make(maxm);
    for (scanf("%d",&te);te;te--){
        scanf("%s%d%d%d",s,&m,&D,&K);m/=D;
        for (int i=1;i<=m;i++) sum[i]=ADD(sum[i-1],Pow(i,K));
        yu=0;fl=false;
        for (int i=0;s[i];i++){
            yu=yu*10+s[i]-48;
            if (yu>phi) fl=true;
            yu%=phi;
        }
        ans=0;
        for (int i=1;i<=m;i++){
            int A=MUL(u[i],Count(ADD(sum[i],MOD-sum[i-1])));
            ans=ADD(ans,MUL(A,Count(sum[m/i])));
        }
        ans=MUL(ans,Count(Pow(D,K)));
        printf("%d\n",ans);
    }
    return 0;
}