MOD = 998244353
t = int(input())
for _ in range(t):
    n, a = map(int, input().split())
    if a == 1:
        print((n * (n - 1) // 2) % MOD)
        continue
    t = []
    m = n
    while m > 0:
        t.append(m % a)
        m //= a
    t.reverse()
    m = len(t)
    s = sum(t)
    x = 0
    y = 0
    ans = 0
    for i in range(m):
        x *= a
        x += t[i]
        s -= t[i]
        k = x * (x - y) - (x * (x + 1) // 2 - y * (y + 1) // 2)
        ans += k + (s + m - i - 1) * (x - y)
        y = x
    print(ans % MOD)