#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto& i:a)
#define ff first 
#define ss second 
#define all(a) begin(a),end(a)
#define allr(a) rbegin(a),rend(a)
#define pb push_back
using ll =long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
template<class T> inline bool chmin(T& a,T b){return a>b?a=b,1:0;}
template<class T> inline bool chmax(T& a,T b){return a<b?a=b,1:0;}

const int INFI=numeric_limits<int>::max()/2;
const ll INFL=numeric_limits<ll>::max()/2;
template <std::uint_fast64_t Modulus> class modint {
    using u64 = std::uint_fast64_t;

public:
    u64 a;

    constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
    constexpr u64 &val() noexcept { return a; }
    constexpr const u64 &val() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
        a += rhs.a;
        if (a >= Modulus) {
            a -= Modulus;
        }
        return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
        if (a < rhs.a) {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
        u64 exp = Modulus - 2;
        while (exp) {
        if (exp % 2) {
          *this *= rhs;
        }
        rhs *= rhs;
        exp /= 2;
        }
        return *this;
    }
};
using mint9=modint<998244353>;
using mint1=modint<1000000007>;

ll n,a;
void solve(){
    if(a==1){
        mint9 ans=n;ans*=(n-1);
        ans/=2;
        cout<<ans.val()<<endl;
        return ;
    }
    vector<ll> c;
    ll n2=n;
    while(n>0){
        c.pb(n%a);
        n/=a;
    }
    n=n2;
    ll cur{0};
    ll pre{0};
    mint9 ans=0;
    rrep(k,c.size()-1,0){
        if(cur!=n){
            double p=cur;
            p+=c[k];
            if(p>INFL){
                cur=n;
            }else {
                cur+=c[k];
            }
        }
        //pre<i<=cur
        mint9 sum=cur;
        rep(i,0,k)sum+=c[i];
        {
            mint9 diff=cur-pre;
            ans+=sum*diff;
            mint9 wa=cur;wa+=pre;
            mint9 tmp=diff*(wa+1);tmp/=2;
            ans-=tmp;
            ans+=diff*k;
        }

        //cout<<ans.val()<<' ';
        pre=cur;
        if(cur!=n){
            double p=cur;
            p*=a;
            if(p>INFL){
                cur=n;
            }else{
                cur*=a;
            }
        }else{
            break;
        }
    }
    //cout<<endl;
    cout<<ans.val()<<endl;
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n>>a;
        solve();
    }
    return 0;
}
/*

*/