## https://yukicoder.me/problems/no/3118

MOD = 998244353

def sum2(y):
    ans = y % MOD
    ans *= (y + 1) % MOD
    ans %= MOD
    ans *= pow(2, MOD - 2, MOD)
    ans %= MOD
    return ans

def to_number(array0, A):
    if array0 == 0:
        return 0

    ans = 0
    powa = 1
    for x in array0:
        ans += (x * powa) % MOD
        ans %= MOD

        powa *= A
        powa %= MOD
    return ans


def solve(N, A):
    if A == 1:
        ans = N % MOD
        ans *= (N - 1) % MOD
        ans %= MOD
        ans *= pow(2, MOD - 2, MOD)
        ans %= MOD
        return ans
    else:
        # NをAの冪で表現
        array = []
        while N > 0:
            array.append(N % A)

            N //= A

        answer = 0        
        array0 = array.copy()
        y0 = 0
        z = 0
        for _ in range(len(array)):
            y = array0[0]
            array0[0] = 0
            
            answer += sum2(y)
            answer %= MOD
            answer += (y0 * (y + 1)) % MOD
            answer %= MOD
            z = (y0 + y) % MOD

            # 割る
            array1 = array0[1:].copy() if len(array0) > 1 else 0

            n0 = to_number(array0, A)
            n1 = to_number(array1, A)

            p0 = n0 - (n1 + 1)
            x = sum2(p0)
            x += (p0 * (y + y0)) % MOD
            x %= MOD
            answer += x
            answer %= MOD

            array0 = array1
            y0 += y + 1
            y0 %= MOD
        return answer








def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, A = map(int, input().split())
        ans = solve(N, A)
        answers.append(ans)

    for ans in answers:
        print(ans)

if __name__ == "__main__":
    main()