//Start: 2024-11-12 07:53:25
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=59964251,phi=59870352;
ll ksm(ll a,int k){ll s=1;while(k){if(k&1) s=s*a%mod;a=a*a%mod;k>>=1;}return s;}
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int p[N],tot,mu[N];bool vis[N];
void init(int n){
  mu[1]=1;
  For(i,2,n){
    if(!vis[i]) p[++tot]=i,mu[i]=-1;
    For(j,1,tot){
      int t=i*p[j];if(t>n) break;
      vis[t]=1;mu[t]=-mu[i];
      if(i%p[j]==0){mu[t]=0;break;}
    }
  }
}
char s[N];ll pw;bool flg;
int d,m,k;ll sum[N];
int gcd(int a,int b){
  if(!a||!b) return a|b;
  int az=__builtin_ctz(a);
  int bz=__builtin_ctz(b);
  int z=min(az,bz);
  b>>=bz;
  while(a){
    a>>=az;
    int diff=b-a;
    az=__builtin_ctz(diff);
    if(a<b) b=a;
    a=abs(diff);
  }return b<<z;
}
ll trs(ll x){
  if(gcd(x,mod)==1) return ksm(x,pw);
  return ksm(x,pw+(flg?phi:0));
}
void ljy(){
  scanf("%s",s+1);
  m=read();d=read();k=read();m/=d;
  For(i,1,m) sum[i]=(sum[i-1]+ksm(i,k))%mod;
  int len=strlen(s+1);pw=flg=0;
  For(i,1,len){
    pw=pw*10+s[i]-'0';
    if(pw>=phi) flg=1,pw%=phi;
  }ll ans=0;
  For(i,1,m) ans=(ans+(mod+mu[i])*trs(ksm(i,k)*sum[m/i]%mod))%mod;
  printf("%lld\n",ans*trs(ksm(d,k))%mod);
}
signed LJY(){init(N-5);int T=read();while(T--) ljy();}