import collections

MOD = 998244353

def solve():
    N, A = map(int, input().split())

    if A == 1:
        # A=1の場合、操作は+1のみなので f(K) = N - K
        # 総和は sum_{K=1 to N} (N-K) = sum_{j=0 to N-1} j = (N-1) * N / 2
        N_mod = N % MOD
        N_minus_1_mod = (N - 1) % MOD
        inv2 = pow(2, MOD - 2, MOD)
        ans = (N_mod * N_minus_1_mod) % MOD
        ans = (ans * inv2) % MOD
        print(ans)
        return

    # BFSで f(K) の総和を計算
    dist = {N: 0}
    q = collections.deque([N])
    total_sum = 0
    
    while q:
        u = q.popleft()
        c = dist[u]
        
        total_sum = (total_sum + c) % MOD
        
        # 操作1: -1
        v1 = u - 1
        if v1 > 0 and v1 not in dist:
            dist[v1] = c + 1
            q.append(v1)
            
        # 操作2: /A
        if u % A == 0:
            v2 = u // A
            if v2 > 0 and v2 not in dist:
                dist[v2] = c + 1
                q.append(v2)
                
    print(total_sum)


T = int(input())
for _ in range(T):
    solve()