#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 59964251;
const int phi = 59870352;
int add(int a, int b)
{
	return (a + b < mod) ? (a + b) : (a + b - mod);
}
int sub(int a, int b)
{
	return (a - b >= 0) ? (a - b) : (a - b + mod);
}
int mult(int a, int b)
{
	return a * (LL) b % mod;
}
int binpow(int a, LL n)
{
	int res = 1;
	while(n)
	{
		if(n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

const int N = 2e6;
int pr[N], mu[N];


int readN()
{
	string n;
	cin >> n;
	int res = 0;
	FOR(i, 0, SZ(n))
	{
		res = (10 * res + (n[i] - '0')) % phi; 
	}
	return res;
}

int a[N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	mu[1] = 1;
	FOR(p, 2, N)
	{
		if(pr[p] != 0)
			continue;
		for(int j = p; j < N; j += p)
		{
			pr[j] = 1;
			if((j / p) % p == 0)
				mu[j] = 0;
			else
				mu[j] = sub(0, mu[j / p]);
		}
	}
	int t;
	cin >> t;
	while(t--)
	{
		int m, d, k;
		int n = readN();
		cin >> m >> d >> k;
			
		
		m /= d;
		FOR(i, 1, m + 1)
			a[i] = binpow(i, k);
			
		int ans = 0;
		FOR(D, 1, m + 1)
		{
			int sum = 0;
			for(int j = D; j <= m; j += D)
				sum = add(sum, a[j]);
			
			ans = add(ans, mult(mu[D], binpow(sum, n)));	
		}
		ans = mult(ans, binpow(d, 1LL * k * n));
		cout << ans << endl;
	}



	
	return 0;
}