MOD = 998244353

def solve_case(N, A):
    # A=1 の特別扱い
    if A == 1:
        # sum_{K=1..N}(N-K) = N(N-1)/2
        return (N % MOD) * ((N - 1) % MOD) * pow(2, MOD-2, MOD) % MOD

    res = 0
    while N > 0:
        M1 = N // A        # floor(N/A)
        d0 = N - A * M1    # N mod A
        d = N - M1         # 要素数

        # 1) 引き算だけで到達する区間のコスト ∑(N-K)
        #    = d*(d-1)/2
        res = (res + d * (d - 1) // 2) % MOD

        # 2) それ以外 (K≤M1) は d0 回の -1 と 1 回の ÷A が共通
        #    = M1 * (d0 + 1)
        res = (res + M1 * (d0 + 1)) % MOD

        # 再帰的に N ← M1 に縮小
        N = M1

    return res

# 入力読み込み・出力
import sys
input = sys.stdin.readline

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