#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

const int MAXM = 100005;
const int MOD = 59964251;
const int PHI = 59870352;

int pw(int a, int n) {
    if (a == 0) return 0;
    int res = 1;
    for (; n; n >>= 1, a = (ll)a * a % MOD)
        if (n & 1)
            res = (ll)res * a % MOD;
    return res;
}

void add(int &x, int val) {
    x += val;
    if (x >= MOD) x -= MOD;
}

int mu[MAXM], prime[MAXM];

void solve() {
    int n;
    int m, d, k;
    {
        string num;
        cin >> num;
        n = 0;
        for (char c : num) {
            n = ((ll)n * 10 + int(c - '0'));
            if (n >= 2 * PHI) {
                n %= PHI;
                n += PHI;
            }
        }
    }
    cin >> m >> d >> k;
    vector<int> sumk(m + 1);
    for (int i = 1; i <= m; ++i) {
        sumk[i] = pw(i, k);
        add(sumk[i], sumk[i - 1]);
    }
    int ans = 0;
    for (int i = 1; i <= m / d; ++i) {
        int val = pw((ll)pw(i * d, k) * sumk[m / (i * d)] % MOD, n);
        if (mu[i] == 1) add(ans, val);
        else if (mu[i] == -1) add(ans, MOD - val);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    mu[1] = 1;
    for (int i = 1; i < MAXM; ++i)
        for (int j = i + i; j < MAXM; j += i)
            mu[j] -= mu[i];
    int t;
    cin >> t;
    while (t--) {
        solve(); 
    }
}