MOD = 998244353

def modinv(x, m):
    return pow(x, m - 2, m)

def solve(N, A):
    if A == 1:
        # Sum of (N - K) for all K from 1 to N
        return (N * (N - 1) // 2) % MOD
    
    # Precompute powers of A up to N
    result = 0
    power_A = 1  # Start with A^0 which is 1
    m = 0
    
    while power_A <= N:
        # Current maximum value we can reach with A^m
        next_power = power_A * A
        if next_power > N:
            next_power = N + 1
        
        # Count how many K's fit this block
        # For each K in this block, we will calculate how many steps it takes to reach N
        count_in_block = N // power_A - N // next_power
        
        sum_of_Ks = (N * (N + 1) // 2 - (N // power_A) * (N // power_A + 1) // 2) % MOD
        
        result += (count_in_block * sum_of_Ks) % MOD
        result %= MOD
        
        m += 1
        power_A = next_power
        
    return result

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    T = int(data[0])
    idx = 1
    
    results = []
    
    for _ in range(T):
        N = int(data[idx])
        A = int(data[idx + 1])
        idx += 2
        result = solve(N, A)
        results.append(result)
    
    sys.stdout.write("\n".join(map(str, results)) + "\n")
    
if __name__ == "__main__":
    main()