#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
vector<int> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
long long fact[61], inv_fact[61];

long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b % 2 == 1) res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i=1; i<=60; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[60] = pow_mod(fact[60], MOD-2, MOD);
    for (int i=59; i>=0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precompute();
    int T;
    cin >> T;
    while (T--) {
        long long N, S;
        cin >> N >> S;
        long long mod_S = S % MOD;
        if (mod_S == 0) {
            cout << "0\n";
            continue;
        }
        long long t_mod = (mod_S - 1 + MOD) % MOD;
        long long comb[61];
        comb[0] = 1;
        long long prod = 1;
        for (int m=1; m<=60; m++) {
            prod = prod * (t_mod + m - 1) % MOD;
            comb[m] = prod * inv_fact[m] % MOD;
        }
        long long temp = N;
        long long ans = 1;
        for (int p : primes) {
            if (temp == 1) break;
            if (temp % p!= 0) continue;
            int e = 0;
            while (temp % p == 0) {
                e++;
                temp /= p;
            }
            long long sum_p = 0;
            long long p_pow = 1;
            for (int k=0; k<=e; k++) {
                int m = e - k;
                sum_p = (sum_p + p_pow * comb[m]) % MOD;
                p_pow = p_pow * p % MOD;
            }
            ans = ans * sum_p % MOD;
        }
        ans = ans * mod_S % MOD;
        cout << ans << '\n';
    }
    return 0;
}