#include<bits/stdc++.h>
const int mod = 59964251, ph = 59870352, MAXN = 1e5+5;
int flag = 0;
int read() {
	int x = 0, y = 0; char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48), x %= ph;
		if(!flag) {
			y = (y << 3) + (y << 1) + (c ^ 48);
			if(y >= ph) flag = 1;
		}
		c = getchar();
	}
	return x;
}
int ksm(int a, int b) {
	int ans = 1;
	for(; b; b >>= 1, a = 1ll * a * a % mod) if(b & 1) ans = 1ll * ans * a % mod;
	return ans;
}
int n, m, d, k, t, f[MAXN], mu[MAXN], pri[MAXN], v[MAXN], cnt, sum[MAXN];
void solve() {
	flag = 0, n = read();
	if(flag) n += ph;
	//printf("%d\n", n);
	scanf("%d%d%d", &m, &d, &k), m /= d;
	for(int i = 1; i <= m; ++i) f[i] = (f[i - 1] + ksm(i, k)) % mod;
	for(int i = 1; i <= m; ++i) f[i] = ksm(f[i], n);
	for(int i = 1; i <= m; ++i)
		sum[i] = (sum[i - 1] + 1ll * mu[i] * ksm(ksm(i, k), n) % mod) % mod;
	int ans = 0;
	for(int l = 1, r; l <= m; l = r + 1) {
		r = m / (m / l);
		ans = (ans + 1ll * (sum[r] - sum[l - 1] + mod) * f[m / l] % mod) % mod;
	}
	printf("%lld\n", 1ll * ans * ksm(ksm(d, k), n) % mod);
}
signed main() {
	mu[1] = 1;
	for(int i = 2; i <= 1e5; ++i) {
		if(!v[i]) pri[++cnt] = i, mu[i] = mod - 1;
		for(int j = 1; j <= cnt && i * pri[j] <= 1e5; ++j) {
			v[i * pri[j]] = 1;
			if(i % pri[j]) mu[i * pri[j]] = mod - mu[i];
			else break;
		}
	}
	scanf("%d", &t);
	while(t--) solve();
	return 0;
}