#include using namespace std; #define int long long const int N = 1e7 + 5, mod = 998244353; int x = 1, inv[N], g[N], f[N], cnt = 0; int mypow(int a, int b) { int ans = 1; while (b) { if (b & 1) { ans = ans * a % mod; } a = a * a % mod; b >>= 1; } return ans; } int C(int n, int m) { return f[n] * g[m] % mod * g[n - m] % mod; } void Solve() { int a, b; cin >> a >> b; for (int i = 2; i * i <= a; i++) { while (a % i == 0) { cnt++; a /= i; } } if (a != 1) { cnt++; } if (cnt < b) { cout << "0\n"; } else cout << C(cnt - 1, b - 1) << "\n"; } signed main() { ios::sync_with_stdio(0); cin.tie(0); inv[1] = f[0] = g[0] = 1; for (int i = 1; i <= 10000000; i++) { f[i] = f[i - 1] * i % mod; if (i > 1) inv[i] = inv[mod % i] * (mod - mod / i) % mod; g[i] = g[i - 1] * inv[i] % mod; } int n; cin >> n; for (int i = 1; i <= n; i++) { Solve(); } return 0; } /* .|.|.|.|. 4 * 3 * 2 * 1 */