#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } struct func{int k,b;}; func get(func a,func b){ return {a.k*1ll*b.k%mod,(a.b*1ll*b.k+b.b)%mod}; } func operator+(func a,func b){ return {(a.k+b.k)%mod,(a.b+b.b)%mod}; } struct node{ func k,b,sk,sb; }; node e={{1,0},{1,0},{0,0},{0,0}}; node operator+(node a,node b){return {get(a.k,b.k),get(a.b,b.b),a.sk+get(a.k,b.sk),a.sb+get(a.b,b.sb)};} node qp(node a,ll b){ node res=e; while(b){ if(b&1)res=res+a; a=a+a,b>>=1; }return res; } int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod,b>>=1; }return res; } node calc(ll p,ll q,ll r,ll n,node L,node R){ if(!n)return e; if(p>=q)return calc(p%q,q,r,n,L,qp(L,p/q)+R); ll m=((__int128)p*n+r)/q; if(!m)return qp(R,n); return (qp(R,(q-1-r)/p)+L)+(calc(q,p,(q-1-r)%p,m-1,R,L)+qp(R,n-((__int128)m*q-r-1)/p)); } void slv(){ ll n=read(),k=read(),p=mod+1-read();p%=mod; ll d=__gcd(n,k);n/=d,k/=d; node L={{p,0},{p,0},{0,0},{0,0}},R={{1,0},{1,1},{1,0},{1,1}}; node x=(L+calc(k,n,0,n-1,L,R))+R; vector<int>v={(x.k.k+x.k.b)%mod,x.b.b,(x.sk.k+x.sk.b)%mod,x.sb.b}; // cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<endl; int s0=(mod-v[1])*1ll*qp(v[0]-1,mod-2)%mod; // cout<<"s0 = "<<s0<<endl; int res=(s0*1ll*v[2]+v[3])%mod; res=res*1ll*qp(n%mod,mod-2)%mod; printf("%d\n",res); } int main(){ //freopen("sun.in","r",stdin),freopen("sun.out","w",stdout); int t=read();while(t--)slv(); return 0; }