#include typedef uint64_t u64; typedef int64_t i64; using namespace std; void solve(); int main(){ cout<>T; } for(int i=0;i void turtle_in(T& n){ cin>>n; } template void turtle_in(pair& p){ turtle_in(p.first); turtle_in(p.second); } template void turtle_in(vector& v){ for(auto& u:v){ turtle_in(u); } } template void turtle_out(T& n){ cout< void turtle_out(pair& p){ cout<<"{"; turtle_out(p.first); cout<<", "; turtle_out(p.second); cout<<"}"; } template void turtle_out(vector& v){ for(int i=0;i void turtle_out(vector>& v){ for(int i=0;i void scan(T& n,Args&... args){ turtle_in(n); scan(args...); } void print(){} template void print(T n,Args... args){ turtle_out(n); print(args...); } template void println(T n){ turtle_out(n); cout< void println(T n,Args... args){ turtle_out(n); cout<<" "; println(args...); } template struct modint{ u64 val; modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){} modint operator-(){ return modint(mod-val); } modint operator+(modint rhs){ return modint(*this)+=rhs; } modint operator-(modint rhs){ return modint(*this)-=rhs; } modint operator*(modint rhs){ return modint(*this)*=rhs; } modint operator/(modint rhs){ return modint(*this)/=rhs; } modint &operator+=(modint rhs){ val+=rhs.val; val-=((val>=mod)?mod:0); return (*this); } modint &operator-=(modint rhs){ val+=((val>=1; } return (*this)*=now; } bool operator==(modint rhs){ return val==rhs.val; } bool operator!=(modint rhs){ return val!=rhs.val; } friend std::ostream &operator<<(std::ostream& os,modint x){ return os<<(x.val); } friend std::istream &operator>>(std::istream& is,modint& x){ u64 t; is>>t,x=t; return is; } }; template T power(T a,U n){ T res=1; while(n>0){ if(n%2==1){ res*=a; } a*=a; n/=2; } return res; } template struct genrand{ uniform_int_distribution gen; mt19937 engine; genrand(T a,T b):gen(a,b){ random_device seed_gen; engine.seed(seed_gen()); } T operator()(){ return gen(engine); } }; template struct comb{ vector dat,idat; comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){ for(int i=1;i<=mx;++i){ dat[i]=dat[i-1]*i; } idat[mx]/=dat[mx]; for(int i=mx;i>0;--i){ idat[i-1]=idat[i]*i; } } T operator()(int n,int k){ if(n<0||k<0||n W(N); scan(W); if(M==0){ print(W); return; } i64 sum=0; for(int i=0;i ans(N); i64 G=gcd(M,sum); M/=G,sum/=G; for(int i=0;i