MOD = 998244353
INV2 = (MOD + 1) // 2  # 2 の逆元

def solve_one(N: int, A: int) -> int:
    # A=1 は特別扱い
    if A == 1:
        return (N % MOD) * ((N - 1) % MOD) % MOD * INV2 % MOD

    S1 = 0  # Σ m(K)
    S2 = 0  # Σ [K * A^{m(K)}]
    m = 0
    powA = 1
    L_m = N  # floor(N / A^m)

    # m を 0 から順に増やしつつ、区間ごとにまとめて
    while L_m > 0:
        # 次の区間の上限
        powA_next = powA * A
        L_next = N // powA_next if powA_next <= N else 0

        cnt = L_m - L_next  # この m に属する K の個数

        # S1 に m * cnt を足す
        S1 = (S1 + m * (cnt % MOD)) % MOD

        # 区間 [L_next+1, L_m] の K の総和を求める
        # sum_K = (L_next+1 + L_m) * cnt // 2  を mod 上で
        sumK_mod = (( (L_next + 1 + L_m) % MOD ) * (cnt % MOD) % MOD) * INV2 % MOD

        # S2 に A^m * sumK
        S2 = (S2 + (powA % MOD) * sumK_mod) % MOD

        # 次へ
        m += 1
        powA = powA_next
        L_m = L_next

    # 最終的に Σ f(K) = S1 + N^2 - S2
    N2 = (N % MOD) * (N % MOD) % MOD
    return (S1 + N2 - S2) % MOD

# 入力‐出力
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, A = map(int, input().split())
    print(solve_one(N, A))