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
    ans=0
    now=0
    pos=N
    while True:
        lw=pos//A
        rng=pos-lw
        ans+=rng*now+rng*(rng-1)//2
        now+=1+(pos%A)
        pos=lw
        if pos==0:
            break
    print(ans%MOD)