#include <bits/stdc++.h>
using namespace std;
using u128 = unsigned __int128;

const long long M = 998244353;
const long long INV2 = (M + 1) / 2;

long long solve(long long N, long long A) {
    long long n_mod = N % M;
    if (A == 1) {
        return n_mod * ((N - 1) % M) % M * INV2 % M;
    }

    // B[m] = A^m
    vector<unsigned long long> B;
    B.reserve(64);
    u128 p = 1;
    while (p <= (u128)N) {
        B.push_back((unsigned long long)p);
        p = p * A;
    }
    int L = B.size();

    // r[m] = floor(N / B[m])
    vector<unsigned long long> r(L + 1);
    for (int i = 0; i < L; i++) r[i] = N / B[i];
    r[L] = 0;

    long long ans = 0;
    for (int i = 0; i < L; i++) {
        unsigned long long l = r[i + 1] + 1;
        unsigned long long rr = r[i];
        if (l > rr) continue;
        unsigned long long K = rr - r[i + 1];
        long long Kmod = K % M;
        // sum of k from l to rr
        long long sum_k = ((l + rr) % M) * Kmod % M * INV2 % M;

        long long term1 = (long long)i % M * Kmod % M;
        long long term2 = n_mod * Kmod % M;
        long long Bmod = B[i] % M;
        long long term3 = Bmod * sum_k % M;

        ans = (ans + term1 + term2 - term3) % M;
    }
    if (ans < 0) ans += M;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long N, A;
        cin >> N >> A;
        cout << solve(N, A) << "\n";
    }
    return 0;
}