#include using namespace atcoder; using mint = modint998244353; //using mint = modint1000000007; //using mint = modint;//mint::set_mod(MOD); const long long MOD = 998244353; //const long long MOD = 1000000007; #include #define rep(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define repeq(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++) #define repreq(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--) #define each(a,b) for(auto& (a):(b)) #define endl '\n' #define cYes cout<<"Yes"<()) #define pb push_back #define mp make_pair #define mt make_tuple #define tget(a,b) get(a) #define FI first #define SE second #define ALL(v) (v).begin(),(v).end() #define INFLL 3000000000000000100LL #define INF 1000000100 #define PI acos(-1.0L) #define TAU (PI*2.0L) using namespace std; typedef long long ll; typedef pair Pll; typedef tuple Tlll; typedef vector Vi; typedef vector VVi; typedef vector Vl; typedef vector VVl; typedef vector VVVl; typedef vector VTlll; typedef vector Vm; typedef vector VVm; typedef vector Vs; typedef vector Vd; typedef vector Vc; typedef vector Vb; typedef vector VPll; typedef priority_queue PQl; typedef priority_queue,greater> PQlr; /* print */ template ostream& operator<<(ostream& os,const vector &V){ int N=V.size();if(N==0){os< ostream& operator<<(ostream& os,const vector> &V){ int N=V.size();rep(i,0,N)os< ostream& operator<<(ostream&os,pairconst&P){os<void Vin(vector &v){int n=v.size();rep(i,0,n)cin>>v[i];} templateint SMALLER(vector &a,T x){ return lower_bound(a.begin(),a.end(),x)-a.begin();} templateint orSMALLER(vector &a,T x){ return upper_bound(a.begin(),a.end(),x)-a.begin();} templateint BIGGER(vector&a,T x){return a.size()-orSMALLER(a,x);} templateint orBIGGER(vector&a,T x){return a.size()-SMALLER(a,x);} templateint COUNT(vector &a,T x){ return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} templatebool chmax(T &a,T b) {if(abool chmin(T &a,T b) {if(a>b){a=b;return 1;}return 0;} templatevoid press(T &v){v.erase(unique(ALL(v)),v.end());} templatevector zip(vector b){pair p[b.size()+10]; int a=b.size();vector l(a);for(int i=0;ivector vis(vector &v){ vector S(v.size()+1);rep(i,1,S.size())S[i]+=v[i-1]+S[i-1];return S;} ll dem(ll a,ll b){return((a+b-1)/(b));} ll dtoll(double d,int g){return round(d*pow(10,g));} const double EPS = 1e-10; void init(){ cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cout<> q; while(q--) sol(); return 0; }