#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using ll   = long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, a, b) for (ll i = (a); i < (b); i++)
bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }
vector<ll> sin45 = {0, 1, 1, 1, 0, -1, -1, -1}, cos45 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<ll> dx = {0, 1, 0, -1};
vector<ll> dy = {1, 0, -1, 0};
#define ft first
#define sd second
#define all(x) std::begin(x), std::end(x)
#define mp(a, b) make_pair(a, b)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb(x) push_back(x)
#define so(z) sort(z.begin(), z.end())
#define sor(z) sort(z.rbegin(), z.rend())
#define vec vector<ll>
#define vecc vector<vector<ll>>

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll t;
    cin >> t;

    rep(i, t) {
        ll n, a;
        cin >> n >> a;

        mint ans = 0;
        ll k   = 1;
        vector<ll> pow;

        if (a == 1) {
            cout << (mint(n) * mint(n - 1) / mint(2)).val() << endl;
            continue;
        }

        while (k <= n) {
            pow.pb(k);
            k *= a;
        }

        reverse(all(pow));
        ll m = pow.size();

        ll bfr = 1; // どこまで足したか

        for (auto x : pow) {

            ll cnt = n / x - bfr + 1;

            ll aft = (n / x) * x;

            ans += mint(cnt * (m - 1) - (mint(aft) + mint(bfr * mint(x))) * cnt / 2 + mint(n) * mint(cnt));
            m--;

            // cout << "cnt: " << cnt << " m: " << m << " aft: " << aft << " bfr: " << bfr << endl;
            // cout << "x: " << x << " ans: " << ans << endl;
            // cout << "------------------------" << endl;
            bfr += cnt;
        }

        cout << ans.val() << endl;
    }
}