from functools import lru_cache
mod = 998244353
@lru_cache(maxsize=None)
def A344527_T(n, k):
    if n == 0:
        return 0
    c, j, k1 = 1, 2, n//2
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A344527_T(k1, k)
        c %= mod
        j, k1 = j2, n//j2
    return (n*(pow(n, k-1, mod)-1)-c+j) % mod
def A332468(n): return A344527_T(n, n)

def solve():
    n, m = map(int, input().split())
    print(A344527_T(m, n))

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == '__main__':
    main()

