#include <bits/stdc++.h>

#define ll long long
#define mod 30000001
#define L 110
#define N 10000010

ll ipow(ll b, ll e){
    if(e == 0) return 1;
    if(e == 1) return b;
    if(e & 1) return ipow(b, e - 1) * b % mod;
    return ipow(b * b % mod, e >> 1);
}

ll inv[L + 2];
ll A[L + 1];
ll B[L + 1];
ll C[L + 1][L + 1];
ll P[L + 1];
ll G[N + 1];

int main(){
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= L + 1; i++){
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    for(int i = 0; i <= L; i++){
        for(int m = 0; m <= i; m++){
            A[m] = inv[m + 1];
            for(int j = m; j; j--){
                A[j - 1] = j * (A[j - 1] - A[j]) % mod;
            }
        }
        B[i] = A[0];
    }
    G[0] = 0;
    for(int n = 0; n <= L; n++){
        for(int r = 0; r <= L; r++){
            if(r > n){
                C[n][r] = 0;
            } else if(r == 0 or r == n){
                C[n][r] = 1;
            } else{
                C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % mod;
            }
        }
    }
    int z;
    scanf("%d", &z);
    while(z--){
        int n, d;
        scanf("%d%d", &n, &d);
        int c = int(fmin(n, pow(n, 2./3) * pow(log(n + 1), 1./3) * 2)) + 1;
        for(int i = 1; i < c; i++){
            G[i] = ipow(i, d) - ipow(i - 1, d);
        }
        for(int i = 1; i < c; i++){
            G[i] %= mod;
            for(int j = i << 1; j < c; j += i){
                G[j] -= G[i];
            }
            G[i] += G[i - 1];
            G[i] %= mod;
        }
        for(int k = n / c; k; k--){
            int i = n / k;
            int u = int(sqrt(i)) + 1;
            ll t = ipow(i, d);
            for(int g = i / u; g > 1; g--){
                t -= G[i / g];
            }
            t %= mod;
            for(int v = 1; v < u; v++){
                t -= (i / v) * (G[v] - G[v - 1]);
                t %= mod;
            }
            t += (i / u) * G[u - 1];
            G[i] = t % mod;
        }
        int q;
        scanf("%d", &q);
        while(q--){
            int l;
            scanf("%d", &l);
            ll t;
            if(l == 0){
                t = ipow(n, d);
            } else{
                for(int k = 0; k <= l; k++){
                    P[k] = C[l + 1][k] * B[k] % mod;
                }
                ll res;
                #define set_F(_w) do {\
                    ll w = (_w);\
                    res = 0;\
                    for(int k = 0; k <= l; k++){\
                        res += P[k];\
                        res *= w;\
                        res %= mod;\
                    }\
                } while(0)
                int u = int(sqrt(n / l)) + 1;
                t = 0;
                for(int v = 1; v < u; v++){
                    set_F(n / v);
                    t += res * (G[v] - G[v - 1]);
                    t %= mod;
                }
                set_F(n / u);
                t -= res * G[u - 1];
                t %= mod;
                t *= inv[l + 1];
                t %= mod;
                for(int g = n / u; g; g--){
                    t += ipow(g, l) * G[n / g];
                    t %= mod;
                }
            }
            if(t < 0) t += mod;
            printf("%lld\n", t);
        }
    }
}