#include<bits/stdc++.h> #define ll long long #define i128 __int128_t using namespace std; const int mod=998244353; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} int qp(int a,ll b){ int x=1; while(b){ if(b&1) x=1ll*x*a%mod; a=1ll*a*a%mod;b>>=1; }return x; } int mulv; struct Node{ int U,R,PW,SPW,SUM,SUM2; Node(){U=0,R=0,PW=1,SPW=0,SUM=0,SUM2=0;} Node(int _U,int _R,int _PW,int _SPW,int _SUM,int _SUM2){U=_U,R=_R,PW=_PW,SPW=_SPW,SUM=_SUM,SUM2=_SUM2;} Node operator+(const Node &b){ return Node( (U+b.U)%mod, (R+b.R)%mod, 1ll*PW*b.PW%mod, (SPW+1ll*b.SPW*PW)%mod, (SUM+(b.SUM+1ll*b.SPW*U)%mod*PW)%mod, (SUM2+(b.SUM2+1ll*b.SPW*R)%mod*PW)%mod); } };Node up,rt; Node fadd(Node a,ll b){ Node x=Node(); while(b){ if(b&1) x=x+a; b>>=1;a=a+a; }return x; } //(px+r)/q U->A R->B Node calc(ll p,ll q,ll r,ll n,Node A,Node B){ if(n==0) return Node(); if(p>=q) return calc(p%q,q,r,n,A,fadd(A,p/q)+B); ll m=((i128)(p)*n+r)/q; if(m==0) return fadd(B,n); return fadd(B,(q-r-1)/p)+A+calc(q,p,(q-r-1)%p,m-1,B,A)+fadd(B,n-((i128)(q)*m-r-1)/p); } ll n,k,p; int calcans(int val){ int pw=qp(mod+1-p,k);n%=mod; //cout<<"tmp:"<<1ll*(1ll*(1ll*val*p)%mod*qp(mod+1-pw,mod-2))%mod*qp(n,mod-2)%mod<<endl; return 1ll*(1ll*(1ll*val*p+1ll*n*n%mod*pw)%mod*qp(mod+1-pw,mod-2))%mod*qp(n,mod-2)%mod; } namespace sub1{ const int N=2e5+10; int pwl[N]; void main(){ //pwl[0]=1; //for(int i=1;i<=n;i++) pwl[i]=1ll*pwl[i-1]*(mod+1-p)%mod; int iv=qp(p,mod-2); /*int tval=0; for(int i=1;i<=n;i++){ ll v=1ll*k*i-1; int v1=1ll*n*(mod+1-pwl[v/n])%mod*iv%mod; int v2=1ll*(v-(v/n)*n+1)%mod*pwl[v/n]%mod; tval=(tval+(v1+v2)%mod)%mod; }tval=mod-tval;tval=(tval+1ll*n*(n+1)%mod*(mod+1-pwl[k])%mod*iv)%mod; //cout<<1ll*n*(n+1)%mod*(mod+1-pwl[k])%mod*iv%mod<<endl; */ up=Node(1,0,(mod+1-p)%mod,0,0,0);rt=Node(0,1,1,1,0,1); Node res=calc(k,n,k-1,n-1,up,rt);res.SPW=(res.SPW+1)%mod; int val=1ll*(n%mod)*iv%mod*(mod+n%mod-res.SPW)%mod; val=(val+1ll*k%mod*(res.SUM2+res.SPW))%mod; val=(val+mod-1ll*n%mod*res.SUM%mod)%mod; val=mod-val;val=(val+1ll*n%mod*(n%mod+1)%mod*(mod+1-qp(mod+1-p,k))%mod*iv)%mod; //cout<<res.SPW<<endl; //cout<<val<<' '<<tval<<endl; //cout<<val<<endl; //cout<<"val:"<<3ll*val%mod<<endl; cout<<calcans(val)<<endl; } } namespace sub2{ void main(){ int val=1ll*(n/k+1)%mod*(n%mod)%mod*qp(2,mod-2)%mod; //cout<<"val:"<<val<<endl; n%=mod;k%=mod; //cout<<(1ll*val*qp(n,mod-2))%mod<<endl; int ans=(1ll*val*qp(n,mod-2)+1ll*(mod+1-p)*n%mod*qp(1ll*k%mod*p%mod,mod-2))%mod; cout<<ans<<endl; } } namespace sub3{ void main(){ ll T=n/k+1; int ans=1ll*((n%k)+1ll*(n/k*k)%mod*qp(2,mod-2))%mod*(T%mod)%mod*qp(n%mod,mod-2)%mod; cout<<ans<<endl; } } int Tc=0; void slv(){ cin>>n>>k>>p; if(n<=2.1e5&&Tc<=15) sub1::main(); else if(n%k==0) sub2::main(); else if(p==1) sub3::main(); else sub1::main(); } int main(){ //freopen("sun.in","r",stdin); //freopen("sun.out","w",stdout); int t;cin>>t;Tc=t; while(t--) slv(); return 0; }