import math
import sympy

MOD = 998244353

Q = int(input())
cnt = 0
for _ in range(Q):
    A, B = map(int, input().split())
    cnt += sum(sympy.factorint(A).values())
    print(math.comb(cnt-1, B-1)%MOD)