#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 struct NTT{ typedef modint mint; mint g=0; int limit=0; vector zeta; mint power_NTT(mint a,u64 n){ mint res=1; while(n){ res*=((n&1)?a:1); a*=a; n>>=1; } return res; } NTT(){ for(g=2;;g+=1){ if(power_NTT(g,(mod-1)>>1)!=1){ break; } } u64 now=(mod-1); while(!(now&1)){ now>>=1; ++limit; } zeta.resize(limit+1,1); zeta[limit]=power_NTT(g,now); for(int i=limit-1;i>=0;--i){ zeta[i]=zeta[i+1]*zeta[i+1]; } } void dft(vector& f,int cnt){ for(int i=0;i<(1<>k)&1)<<(cnt-1-k); } if(i mul_naive(vector a,vector b){ vector res(a.size()+b.size()-1); for(int i=0;i mul_fast(vector a,vector b){ int cnt=0,siz=1,mxsiz=a.size()+b.size()-1; while(siz mul(vector a,vector b){ if(min(a.size(),b.size())<=64){ return mul_naive(a,b); } else{ return mul_fast(a,b); } } }; template struct Poly{ typedef modint mint; NTT ntt; vector val; Poly():val({0}){} Poly(mint t):val({t}){} Poly(int siz):val(max(1,siz)){} Poly(initializer_list> init):val(init){} Poly(vector init):val(init){} mint &operator[](int i){ return val[i]; } int size(){ return val.size(); } void resize(int siz){ val.resize(siz); } Poly operator+(Poly rhs){ return Poly(*this)+=rhs; } Poly operator-(Poly rhs){ return Poly(*this)-=rhs; } Poly operator*(Poly rhs){ return Poly(*this)*=rhs; } Poly operator/(Poly rhs){ return Poly(*this)/=rhs; } Poly operator%(Poly rhs){ return Poly(*this)%=rhs; } Poly operator-(){ for(mint& v:val){ v=mint(0)-v; } return (*this); } Poly operator+=(Poly rhs){ resize(max(this->size(),rhs.size())); for(int i=0;isize(),rhs.size())); for(int i=0;i0;--i){ if(val[i]==0){ val.pop_back(); } else{ return; } } } vector multieval(vector> a){ int siz=1; while(siz> t(siz*2-1,{1}); for(int i=0;i=0;--i){ t[i]=t[2*i+1]*t[2*i+2]; } vector> g(siz*2-1); g[0]=(*this)%t[0]; for(int i=1;i> res(a.size()); for(int i=0;i> a){ int siz=1; while(siz> res(siz*2-1,{1}); for(int i=0;i=0;--i){ res[i]=res[2*i+1]*res[2*i+2]; } (*this)=res[0]; } void lagrange_interpolation(vector x,vector y){ int N=x.size(); vector> h(N); for(int i=0;i g; g.product(h); Poly g_=g; g_.diffrent(); vector t=g_.multieval(x); for(int i=0;i> den(2*N-1),num(2*N-1,{1}); for(int i=0;i=0;--i){ den[i]=den[2*i+1]*den[2*i+2]; num[i]=num[2*i+1]*den[2*i+2]+num[2*i+2]*den[2*i+1]; } (*this)=num[0]; } void diffrent(){ Poly f(val.size()-1); for(int i=1;i mp; mp["A"]="A#",mp["C"]="C#",mp["E"]="E#",mp["F"]="F#",mp["G"]="G#"; mp["E"]="F",mp["B"]="C"; println(mp[S]); }