#define PROBLEM "https://judge.yosupo.jp/problem/addition_of_big_integers"
//#include"../../template/template.hpp"//#include"../../math/bigint.hpp"//#include"../../misc/fastio.hpp"usingnamespaceNyaan;voidq(){intt;rd(t);while(t--){stringbuf1,buf2;rd(buf1,buf2);biginta=buf1,b=buf2;wtn((a+b).to_string());}}voidNyaan::solve(){intt=1;// in(t);while(t--)q();}
#line 1 "verify/verify-yosupo-math/yosupo-addition-of-big-integers.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/addition_of_big_integers"
//#line 2 "template/template.hpp"
usingnamespacestd;// intrinstic#include<immintrin.h>#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cfenv>
#include<cfloat>
#include<chrono>
#include<cinttypes>
#include<climits>
#include<cmath>
#include<complex>
#include<cstdarg>
#include<cstddef>
#include<cstdint>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<fstream>
#include<functional>
#include<initializer_list>
#include<iomanip>
#include<ios>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<stack>
#include<streambuf>
#include<string>
#include<tuple>
#include<type_traits>
#include<typeinfo>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>// utility#line 1 "template/util.hpp"
namespaceNyaan{usingll=longlong;usingi64=longlong;usingu64=unsignedlonglong;usingi128=__int128_t;usingu128=__uint128_t;template<typenameT>usingV=vector<T>;template<typenameT>usingVV=vector<vector<T>>;usingvi=vector<int>;usingvl=vector<longlong>;usingvd=V<double>;usingvs=V<string>;usingvvi=vector<vector<int>>;usingvvl=vector<vector<longlong>>;template<typenameT>usingminpq=priority_queue<T,vector<T>,greater<T>>;template<typenameT,typenameU>structP:pair<T,U>{template<typename...Args>P(Args...args):pair<T,U>(args...){}usingpair<T,U>::first;usingpair<T,U>::second;P&operator+=(constP&r){first+=r.first;second+=r.second;return*this;}P&operator-=(constP&r){first-=r.first;second-=r.second;return*this;}P&operator*=(constP&r){first*=r.first;second*=r.second;return*this;}template<typenameS>P&operator*=(constS&r){first*=r,second*=r;return*this;}Poperator+(constP&r)const{returnP(*this)+=r;}Poperator-(constP&r)const{returnP(*this)-=r;}Poperator*(constP&r)const{returnP(*this)*=r;}template<typenameS>Poperator*(constS&r)const{returnP(*this)*=r;}Poperator-()const{returnP{-first,-second};}};usingpl=P<ll,ll>;usingpi=P<int,int>;usingvp=V<pl>;constexprintinf=1001001001;constexprlonglonginfLL=4004004004004004004LL;template<typenameT>intsz(constT&t){returnt.size();}template<typenameT,typenameU>inlineboolamin(T&x,Uy){return(y<x)?(x=y,true):false;}template<typenameT,typenameU>inlineboolamax(T&x,Uy){return(x<y)?(x=y,true):false;}template<typenameT>inlineTMax(constvector<T>&v){return*max_element(begin(v),end(v));}template<typenameT>inlineTMin(constvector<T>&v){return*min_element(begin(v),end(v));}template<typenameT>inlinelonglongSum(constvector<T>&v){returnaccumulate(begin(v),end(v),0LL);}template<typenameT>intlb(constvector<T>&v,constT&a){returnlower_bound(begin(v),end(v),a)-begin(v);}template<typenameT>intub(constvector<T>&v,constT&a){returnupper_bound(begin(v),end(v),a)-begin(v);}constexprlonglongTEN(intn){longlongret=1,x=10;for(;n;x*=x,n>>=1)ret*=(n&1?x:1);returnret;}template<typenameT,typenameU>pair<T,U>mkp(constT&t,constU&u){returnmake_pair(t,u);}template<typenameT>vector<T>mkrui(constvector<T>&v,boolrev=false){vector<T>ret(v.size()+1);if(rev){for(inti=int(v.size())-1;i>=0;i--)ret[i]=v[i]+ret[i+1];}else{for(inti=0;i<int(v.size());i++)ret[i+1]=ret[i]+v[i];}returnret;};template<typenameT>vector<T>mkuni(constvector<T>&v){vector<T>ret(v);sort(ret.begin(),ret.end());ret.erase(unique(ret.begin(),ret.end()),ret.end());returnret;}template<typenameF>vector<int>mkord(intN,Ff){vector<int>ord(N);iota(begin(ord),end(ord),0);sort(begin(ord),end(ord),f);returnord;}template<typenameT>vector<int>mkinv(vector<T>&v){intmax_val=*max_element(begin(v),end(v));vector<int>inv(max_val+1,-1);for(inti=0;i<(int)v.size();i++)inv[v[i]]=i;returninv;}vector<int>mkiota(intn){vector<int>ret(n);iota(begin(ret),end(ret),0);returnret;}template<typenameT>Tmkrev(constT&v){Tw{v};reverse(begin(w),end(w));returnw;}template<typenameT>boolnxp(T&v){returnnext_permutation(begin(v),end(v));}// 返り値の型は入力の T に依存// i 要素目 : [0, a[i])template<typenameT>vector<vector<T>>product(constvector<T>&a){vector<vector<T>>ret;vector<T>v;autodfs=[&](autorc,inti)->void{if(i==(int)a.size()){ret.push_back(v);return;}for(intj=0;j<a[i];j++)v.push_back(j),rc(rc,i+1),v.pop_back();};dfs(dfs,0);returnret;}// F : function(void(T&)), mod を取る操作// T : 整数型のときはオーバーフローに注意するtemplate<typenameT>TPower(Ta,longlongn,constT&I,constfunction<void(T&)>&f){Tres=I;for(;n;f(a=a*a),n>>=1){if(n&1)f(res=res*a);}returnres;}// T : 整数型のときはオーバーフローに注意するtemplate<typenameT>TPower(Ta,longlongn,constT&I=T{1}){returnPower(a,n,I,function<void(T&)>{[](T&)->void{}});}template<typenameT>TRev(constT&v){Tres=v;reverse(begin(res),end(res));returnres;}template<typenameT>vector<T>Transpose(constvector<T>&v){usingU=typenameT::value_type;if(v.empty())return{};intH=v.size(),W=v[0].size();vectorres(W,T(H,U{}));for(inti=0;i<H;i++){for(intj=0;j<W;j++){res[j][i]=v[i][j];}}returnres;}template<typenameT>vector<T>Rotate(constvector<T>&v,intclockwise=true){usingU=typenameT::value_type;intH=v.size(),W=v[0].size();vectorres(W,T(H,U{}));for(inti=0;i<H;i++){for(intj=0;j<W;j++){if(clockwise){res[W-1-j][i]=v[i][j];}else{res[j][H-1-i]=v[i][j];}}}returnres;}}// namespace Nyaan#line 58 "template/template.hpp"
// bit operation#line 1 "template/bitop.hpp"
namespaceNyaan{__attribute__((target("popcnt")))inlineintpopcnt(constu64&a){return__builtin_popcountll(a);}inlineintlsb(constu64&a){returna?__builtin_ctzll(a):64;}inlineintctz(constu64&a){returna?__builtin_ctzll(a):64;}inlineintmsb(constu64&a){returna?63-__builtin_clzll(a):-1;}template<typenameT>inlineintgbit(constT&a,inti){return(a>>i)&1;}template<typenameT>inlinevoidsbit(T&a,inti,boolb){if(gbit(a,i)!=b)a^=T(1)<<i;}constexprlonglongPW(intn){return1LL<<n;}constexprlonglongMSK(intn){return(1LL<<n)-1;}}// namespace Nyaan#line 61 "template/template.hpp"
// inout#line 1 "template/inout.hpp"
namespaceNyaan{template<typenameT,typenameU>ostream&operator<<(ostream&os,constpair<T,U>&p){os<<p.first<<" "<<p.second;returnos;}template<typenameT,typenameU>istream&operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;returnis;}template<typenameT>ostream&operator<<(ostream&os,constvector<T>&v){ints=(int)v.size();for(inti=0;i<s;i++)os<<(i?" ":"")<<v[i];returnos;}template<typenameT>istream&operator>>(istream&is,vector<T>&v){for(auto&x:v)is>>x;returnis;}istream&operator>>(istream&is,__int128_t&x){stringS;is>>S;x=0;intflag=0;for(auto&c:S){if(c=='-'){flag=true;continue;}x*=10;x+=c-'0';}if(flag)x=-x;returnis;}istream&operator>>(istream&is,__uint128_t&x){stringS;is>>S;x=0;for(auto&c:S){x*=10;x+=c-'0';}returnis;}ostream&operator<<(ostream&os,__int128_tx){if(x==0)returnos<<0;if(x<0)os<<'-',x=-x;stringS;while(x)S.push_back('0'+x%10),x/=10;reverse(begin(S),end(S));returnos<<S;}ostream&operator<<(ostream&os,__uint128_tx){if(x==0)returnos<<0;stringS;while(x)S.push_back('0'+x%10),x/=10;reverse(begin(S),end(S));returnos<<S;}voidin(){}template<typenameT,class...U>voidin(T&t,U&...u){cin>>t;in(u...);}voidout(){cout<<"\n";}template<typenameT,class...U,charsep=' '>voidout(constT&t,constU&...u){cout<<t;if(sizeof...(u))cout<<sep;out(u...);}structIoSetupNya{IoSetupNya(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(7);}}iosetupnya;}// namespace Nyaan#line 64 "template/template.hpp"
// debug#line 1 "template/debug.hpp"
namespaceDebugImpl{template<typenameU,typename=void>structis_specialize:false_type{};template<typenameU>structis_specialize<U,typenameconditional<false,typenameU::iterator,void>::type>:true_type{};template<typenameU>structis_specialize<U,typenameconditional<false,decltype(U::first),void>::type>:true_type{};template<typenameU>structis_specialize<U,enable_if_t<is_integral<U>::value,void>>:true_type{};voiddump(constchar&t){cerr<<t;}voiddump(conststring&t){cerr<<t;}voiddump(constbool&t){cerr<<(t?"true":"false");}voiddump(__int128_tt){if(t==0)cerr<<0;if(t<0)cerr<<'-',t=-t;stringS;while(t)S.push_back('0'+t%10),t/=10;reverse(begin(S),end(S));cerr<<S;}voiddump(__uint128_tt){if(t==0)cerr<<0;stringS;while(t)S.push_back('0'+t%10),t/=10;reverse(begin(S),end(S));cerr<<S;}template<typenameU,enable_if_t<!is_specialize<U>::value,nullptr_t>=nullptr>voiddump(constU&t){cerr<<t;}template<typenameT>voiddump(constT&t,enable_if_t<is_integral<T>::value>*=nullptr){stringres;if(t==Nyaan::inf)res="inf";ifconstexpr(is_signed<T>::value){if(t==-Nyaan::inf)res="-inf";}ifconstexpr(sizeof(T)==8){if(t==Nyaan::infLL)res="inf";ifconstexpr(is_signed<T>::value){if(t==-Nyaan::infLL)res="-inf";}}if(res.empty())res=to_string(t);cerr<<res;}template<typenameT,typenameU>voiddump(constpair<T,U>&);template<typenameT>voiddump(constpair<T*,int>&);template<typenameT>voiddump(constT&t,enable_if_t<!is_void<typenameT::iterator>::value>*=nullptr){cerr<<"[ ";for(autoit=t.begin();it!=t.end();){dump(*it);cerr<<(++it==t.end()?"":", ");}cerr<<" ]";}template<typenameT,typenameU>voiddump(constpair<T,U>&t){cerr<<"( ";dump(t.first);cerr<<", ";dump(t.second);cerr<<" )";}template<typenameT>voiddump(constpair<T*,int>&t){cerr<<"[ ";for(inti=0;i<t.second;i++){dump(t.first[i]);cerr<<(i==t.second-1?"":", ");}cerr<<" ]";}voidtrace(){cerr<<endl;}template<typenameHead,typename...Tail>voidtrace(Head&&head,Tail&&...tail){cerr<<" ";dump(head);if(sizeof...(tail)!=0)cerr<<",";trace(std::forward<Tail>(tail)...);}}// namespace DebugImpl#ifdef NyaanDebug
#define trc(...) \
do { \
cerr << "## " << #__VA_ARGS__ << " = "; \
DebugImpl::trace(__VA_ARGS__); \
} while (0)
#else
#define trc(...) (void(0))
#endif
#ifdef NyaanLocal
#define trc2(...) \
do { \
cerr << "## " << #__VA_ARGS__ << " = "; \
DebugImpl::trace(__VA_ARGS__); \
} while (0)
#else
#define trc2(...) (void(0))
#endif
#line 67 "template/template.hpp"
// macro#line 1 "template/macro.hpp"
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define die(...) \
do { \
Nyaan::out(__VA_ARGS__); \
return; \
} while (0)
#line 70 "template/template.hpp"
namespaceNyaan{voidsolve();}intmain(){Nyaan::solve();}#line 4 "verify/verify-yosupo-math/yosupo-addition-of-big-integers.test.cpp"
//#line 2 "math/bigint.hpp"
#line 10 "math/bigint.hpp"
usingnamespacestd;#line 2 "internal/internal-type-traits.hpp"
#line 4 "internal/internal-type-traits.hpp"
usingnamespacestd;namespaceinternal{template<typenameT>usingis_broadly_integral=typenameconditional_t<is_integral_v<T>||is_same_v<T,__int128_t>||is_same_v<T,__uint128_t>,true_type,false_type>::type;template<typenameT>usingis_broadly_signed=typenameconditional_t<is_signed_v<T>||is_same_v<T,__int128_t>,true_type,false_type>::type;template<typenameT>usingis_broadly_unsigned=typenameconditional_t<is_unsigned_v<T>||is_same_v<T,__uint128_t>,true_type,false_type>::type;#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE(is_broadly_integral);ENABLE_VALUE(is_broadly_signed);ENABLE_VALUE(is_broadly_unsigned);#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
}// namespace internal#line 2 "ntt/arbitrary-ntt.hpp"
#line 2 "modint/montgomery-modint.hpp"
template<uint32_tmod>structLazyMontgomeryModInt{usingmint=LazyMontgomeryModInt;usingi32=int32_t;usingu32=uint32_t;usingu64=uint64_t;staticconstexpru32get_r(){u32ret=mod;for(i32i=0;i<4;++i)ret*=2-mod*ret;returnret;}staticconstexpru32r=get_r();staticconstexpru32n2=-u64(mod)%mod;static_assert(mod<(1<<30),"invalid, mod >= 2 ^ 30");static_assert((mod&1)==1,"invalid, mod % 2 == 0");static_assert(r*mod==1,"this code has bugs.");u32a;constexprLazyMontgomeryModInt():a(0){}constexprLazyMontgomeryModInt(constint64_t&b):a(reduce(u64(b%mod+mod)*n2)){};staticconstexpru32reduce(constu64&b){return(b+u64(u32(b)*u32(-r))*mod)>>32;}constexprmint&operator+=(constmint&b){if(i32(a+=b.a-2*mod)<0)a+=2*mod;return*this;}constexprmint&operator-=(constmint&b){if(i32(a-=b.a)<0)a+=2*mod;return*this;}constexprmint&operator*=(constmint&b){a=reduce(u64(a)*b.a);return*this;}constexprmint&operator/=(constmint&b){*this*=b.inverse();return*this;}constexprmintoperator+(constmint&b)const{returnmint(*this)+=b;}constexprmintoperator-(constmint&b)const{returnmint(*this)-=b;}constexprmintoperator*(constmint&b)const{returnmint(*this)*=b;}constexprmintoperator/(constmint&b)const{returnmint(*this)/=b;}constexprbooloperator==(constmint&b)const{return(a>=mod?a-mod:a)==(b.a>=mod?b.a-mod:b.a);}constexprbooloperator!=(constmint&b)const{return(a>=mod?a-mod:a)!=(b.a>=mod?b.a-mod:b.a);}constexprmintoperator-()const{returnmint()-mint(*this);}constexprmintoperator+()const{returnmint(*this);}constexprmintpow(u64n)const{mintret(1),mul(*this);while(n>0){if(n&1)ret*=mul;mul*=mul;n>>=1;}returnret;}constexprmintinverse()const{intx=get(),y=mod,u=1,v=0,t=0,tmp=0;while(y>0){t=x/y;x-=t*y,u-=t*v;tmp=x,x=y,y=tmp;tmp=u,u=v,v=tmp;}returnmint{u};}friendostream&operator<<(ostream&os,constmint&b){returnos<<b.get();}friendistream&operator>>(istream&is,mint&b){int64_tt;is>>t;b=LazyMontgomeryModInt<mod>(t);return(is);}constexpru32get()const{u32ret=reduce(a);returnret>=mod?ret-mod:ret;}staticconstexpru32get_mod(){returnmod;}};#line 2 "ntt/ntt.hpp"
template<typenamemint>structNTT{staticconstexpruint32_tget_pr(){uint32_t_mod=mint::get_mod();usingu64=uint64_t;u64ds[32]={};intidx=0;u64m=_mod-1;for(u64i=2;i*i<=m;++i){if(m%i==0){ds[idx++]=i;while(m%i==0)m/=i;}}if(m!=1)ds[idx++]=m;uint32_t_pr=2;while(1){intflg=1;for(inti=0;i<idx;++i){u64a=_pr,b=(_mod-1)/ds[i],r=1;while(b){if(b&1)r=r*a%_mod;a=a*a%_mod;b>>=1;}if(r==1){flg=0;break;}}if(flg==1)break;++_pr;}return_pr;};staticconstexpruint32_tmod=mint::get_mod();staticconstexpruint32_tpr=get_pr();staticconstexprintlevel=__builtin_ctzll(mod-1);mintdw[level],dy[level];voidsetwy(intk){mintw[level],y[level];w[k-1]=mint(pr).pow((mod-1)/(1<<k));y[k-1]=w[k-1].inverse();for(inti=k-2;i>0;--i)w[i]=w[i+1]*w[i+1],y[i]=y[i+1]*y[i+1];dw[1]=w[1],dy[1]=y[1],dw[2]=w[2],dy[2]=y[2];for(inti=3;i<k;++i){dw[i]=dw[i-1]*y[i-2]*w[i];dy[i]=dy[i-1]*w[i-2]*y[i];}}NTT(){setwy(level);}voidfft4(vector<mint>&a,intk){if((int)a.size()<=1)return;if(k==1){minta1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}if(k&1){intv=1<<(k-1);for(intj=0;j<v;++j){mintajv=a[j+v];a[j+v]=a[j]-ajv;a[j]+=ajv;}}intu=1<<(2+(k&1));intv=1<<(k-2-(k&1));mintone=mint(1);mintimag=dw[1];while(v){// jh = 0{intj0=0;intj1=v;intj2=j1+v;intj3=j2+v;for(;j0<v;++j0,++j1,++j2,++j3){mintt0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];mintt0p2=t0+t2,t1p3=t1+t3;mintt0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3,a[j1]=t0p2-t1p3;a[j2]=t0m2+t1m3,a[j3]=t0m2-t1m3;}}// jh >= 1mintww=one,xx=one*dw[2],wx=one;for(intjh=4;jh<u;){ww=xx*xx,wx=ww*xx;intj0=jh*v;intje=j0+v;intj2=je+v;for(;j0<je;++j0,++j2){mintt0=a[j0],t1=a[j0+v]*xx,t2=a[j2]*ww,t3=a[j2+v]*wx;mintt0p2=t0+t2,t1p3=t1+t3;mintt0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3,a[j0+v]=t0p2-t1p3;a[j2]=t0m2+t1m3,a[j2+v]=t0m2-t1m3;}xx*=dw[__builtin_ctzll((jh+=4))];}u<<=2;v>>=2;}}voidifft4(vector<mint>&a,intk){if((int)a.size()<=1)return;if(k==1){minta1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}intu=1<<(k-2);intv=1;mintone=mint(1);mintimag=dy[1];while(u){// jh = 0{intj0=0;intj1=v;intj2=v+v;intj3=j2+v;for(;j0<v;++j0,++j1,++j2,++j3){mintt0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];mintt0p1=t0+t1,t2p3=t2+t3;mintt0m1=t0-t1,t2m3=(t2-t3)*imag;a[j0]=t0p1+t2p3,a[j2]=t0p1-t2p3;a[j1]=t0m1+t2m3,a[j3]=t0m1-t2m3;}}// jh >= 1mintww=one,xx=one*dy[2],yy=one;u<<=2;for(intjh=4;jh<u;){ww=xx*xx,yy=xx*imag;intj0=jh*v;intje=j0+v;intj2=je+v;for(;j0<je;++j0,++j2){mintt0=a[j0],t1=a[j0+v],t2=a[j2],t3=a[j2+v];mintt0p1=t0+t1,t2p3=t2+t3;mintt0m1=(t0-t1)*xx,t2m3=(t2-t3)*yy;a[j0]=t0p1+t2p3,a[j2]=(t0p1-t2p3)*ww;a[j0+v]=t0m1+t2m3,a[j2+v]=(t0m1-t2m3)*ww;}xx*=dy[__builtin_ctzll(jh+=4)];}u>>=4;v<<=2;}if(k&1){u=1<<(k-1);for(intj=0;j<u;++j){mintajv=a[j]-a[j+u];a[j]+=a[j+u];a[j+u]=ajv;}}}voidntt(vector<mint>&a){if((int)a.size()<=1)return;fft4(a,__builtin_ctz(a.size()));}voidintt(vector<mint>&a){if((int)a.size()<=1)return;ifft4(a,__builtin_ctz(a.size()));mintiv=mint(a.size()).inverse();for(auto&x:a)x*=iv;}vector<mint>multiply(constvector<mint>&a,constvector<mint>&b){intl=a.size()+b.size()-1;if(min<int>(a.size(),b.size())<=40){vector<mint>s(l);for(inti=0;i<(int)a.size();++i)for(intj=0;j<(int)b.size();++j)s[i+j]+=a[i]*b[j];returns;}intk=2,M=4;while(M<l)M<<=1,++k;setwy(k);vector<mint>s(M);for(inti=0;i<(int)a.size();++i)s[i]=a[i];fft4(s,k);if(a.size()==b.size()&&a==b){for(inti=0;i<M;++i)s[i]*=s[i];}else{vector<mint>t(M);for(inti=0;i<(int)b.size();++i)t[i]=b[i];fft4(t,k);for(inti=0;i<M;++i)s[i]*=t[i];}ifft4(s,k);s.resize(l);mintinvm=mint(M).inverse();for(inti=0;i<l;++i)s[i]*=invm;returns;}voidntt_doubling(vector<mint>&a){intM=(int)a.size();autob=a;intt(b);mintr=1,zeta=mint(pr).pow((mint::get_mod()-1)/(M<<1));for(inti=0;i<M;i++)b[i]*=r,r*=zeta;ntt(b);copy(begin(b),end(b),back_inserter(a));}};#line 5 "ntt/arbitrary-ntt.hpp"
namespaceArbitraryNTT{usingi64=int64_t;usingu128=__uint128_t;constexprint32_tm0=167772161;constexprint32_tm1=469762049;constexprint32_tm2=754974721;usingmint0=LazyMontgomeryModInt<m0>;usingmint1=LazyMontgomeryModInt<m1>;usingmint2=LazyMontgomeryModInt<m2>;constexprintr01=mint1(m0).inverse().get();constexprintr02=mint2(m0).inverse().get();constexprintr12=mint2(m1).inverse().get();constexprintr02r12=i64(r02)*r12%m2;constexpri64w1=m0;constexpri64w2=i64(m0)*m1;template<typenameT,typenamesubmint>vector<submint>mul(constvector<T>&a,constvector<T>&b){staticNTT<submint>ntt;vector<submint>s(a.size()),t(b.size());for(inti=0;i<(int)a.size();++i)s[i]=i64(a[i]%submint::get_mod());for(inti=0;i<(int)b.size();++i)t[i]=i64(b[i]%submint::get_mod());returnntt.multiply(s,t);}template<typenameT>vector<int>multiply(constvector<T>&s,constvector<T>&t,intmod){autod0=mul<T,mint0>(s,t);autod1=mul<T,mint1>(s,t);autod2=mul<T,mint2>(s,t);intn=d0.size();vector<int>ret(n);constintW1=w1%mod;constintW2=w2%mod;for(inti=0;i<n;i++){intn1=d1[i].get(),n2=d2[i].get(),a=d0[i].get();intb=i64(n1+m1-a)*r01%m1;intc=(i64(n2+m2-a)*r02r12+i64(m2-b)*r12)%m2;ret[i]=(i64(a)+i64(b)*W1+i64(c)*W2)%mod;}returnret;}template<typenamemint>vector<mint>multiply(constvector<mint>&a,constvector<mint>&b){if(a.size()==0&&b.size()==0)return{};if(min<int>(a.size(),b.size())<128){vector<mint>ret(a.size()+b.size()-1);for(inti=0;i<(int)a.size();++i)for(intj=0;j<(int)b.size();++j)ret[i+j]+=a[i]*b[j];returnret;}vector<int>s(a.size()),t(b.size());for(inti=0;i<(int)a.size();++i)s[i]=a[i].get();for(inti=0;i<(int)b.size();++i)t[i]=b[i].get();vector<int>u=multiply<int>(s,t,mint::get_mod());vector<mint>ret(u.size());for(inti=0;i<(int)u.size();++i)ret[i]=mint(u[i]);returnret;}template<typenameT>vector<u128>multiply_u128(constvector<T>&s,constvector<T>&t){if(s.size()==0&&t.size()==0)return{};if(min<int>(s.size(),t.size())<128){vector<u128>ret(s.size()+t.size()-1);for(inti=0;i<(int)s.size();++i)for(intj=0;j<(int)t.size();++j)ret[i+j]+=i64(s[i])*t[j];returnret;}autod0=mul<T,mint0>(s,t);autod1=mul<T,mint1>(s,t);autod2=mul<T,mint2>(s,t);intn=d0.size();vector<u128>ret(n);for(inti=0;i<n;i++){i64n1=d1[i].get(),n2=d2[i].get();i64a=d0[i].get();i64b=(n1+m1-a)*r01%m1;i64c=((n2+m2-a)*r02r12+(m2-b)*r12)%m2;ret[i]=a+b*w1+u128(c)*w2;}returnret;}}// namespace ArbitraryNTT#line 14 "math/bigint.hpp"
namespaceMultiPrecisionIntegerImpl{structTENS{staticconstexprintoffset=30;constexprTENS():_tend(){_tend[offset]=1;for(inti=1;i<=offset;i++){_tend[offset+i]=_tend[offset+i-1]*10.0;_tend[offset-i]=1.0/_tend[offset+i];}}longdoubleten_ld(intn)const{assert(-offset<=nandn<=offset);return_tend[n+offset];}private:longdouble_tend[offset*2+1];};}// namespace MultiPrecisionIntegerImpl// 0 は neg=false, dat={} として扱うstructMultiPrecisionInteger{usingM=MultiPrecisionInteger;inlineconstexprstaticMultiPrecisionIntegerImpl::TENStens={};staticconstexprintD=1000000000;staticconstexprintlogD=9;boolneg;vector<int>dat;MultiPrecisionInteger():neg(false),dat(){}MultiPrecisionInteger(booln,constvector<int>&d):neg(n),dat(d){}template<typenameI,enable_if_t<internal::is_broadly_integral_v<I>>*=nullptr>MultiPrecisionInteger(Ix):neg(false){ifconstexpr(internal::is_broadly_signed_v<I>){if(x<0)neg=true,x=-x;}while(x)dat.push_back(x%D),x/=D;}MultiPrecisionInteger(conststring&S):neg(false){assert(!S.empty());if(S.size()==1u&&S[0]=='0')return;intl=0;if(S[0]=='-')++l,neg=true;for(intie=S.size();l<ie;ie-=logD){intis=max(l,ie-logD);longlongx=0;for(inti=is;i<ie;i++)x=x*10+S[i]-'0';dat.push_back(x);}while(!dat.empty()anddat.back()==0)dat.pop_back();}friendMoperator+(constM&lhs,constM&rhs){if(lhs.neg==rhs.neg)return{lhs.neg,_add(lhs.dat,rhs.dat)};if(_leq(lhs.dat,rhs.dat)){// |l| <= |r|autoc=_sub(rhs.dat,lhs.dat);booln=_is_zero(c)?false:rhs.neg;return{n,c};}autoc=_sub(lhs.dat,rhs.dat);booln=_is_zero(c)?false:lhs.neg;return{n,c};}friendMoperator-(constM&lhs,constM&rhs){returnlhs+(-rhs);}friendMoperator*(constM&lhs,constM&rhs){autoc=_mul(lhs.dat,rhs.dat);booln=_is_zero(c)?false:(lhs.neg^rhs.neg);return{n,c};}friendpair<M,M>divmod(constM&lhs,constM&rhs){autodm=_divmod_newton(lhs.dat,rhs.dat);booldn=_is_zero(dm.first)?false:lhs.neg!=rhs.neg;boolmn=_is_zero(dm.second)?false:lhs.neg;return{M{dn,dm.first},M{mn,dm.second}};}friendMoperator/(constM&lhs,constM&rhs){returndivmod(lhs,rhs).first;}friendMoperator%(constM&lhs,constM&rhs){returndivmod(lhs,rhs).second;}M&operator+=(constM&rhs){return(*this)=(*this)+rhs;}M&operator-=(constM&rhs){return(*this)=(*this)-rhs;}M&operator*=(constM&rhs){return(*this)=(*this)*rhs;}M&operator/=(constM&rhs){return(*this)=(*this)/rhs;}M&operator%=(constM&rhs){return(*this)=(*this)%rhs;}Moperator-()const{if(is_zero())return*this;return{!neg,dat};}Moperator+()const{return*this;}friendMabs(constM&m){return{false,m.dat};}boolis_zero()const{return_is_zero(dat);}friendbooloperator==(constM&lhs,constM&rhs){returnlhs.neg==rhs.neg&&lhs.dat==rhs.dat;}friendbooloperator!=(constM&lhs,constM&rhs){returnlhs.neg!=rhs.neg||lhs.dat!=rhs.dat;}friendbooloperator<(constM&lhs,constM&rhs){if(lhs==rhs)returnfalse;return_neq_lt(lhs,rhs);}friendbooloperator<=(constM&lhs,constM&rhs){if(lhs==rhs)returntrue;return_neq_lt(lhs,rhs);}friendbooloperator>(constM&lhs,constM&rhs){if(lhs==rhs)returnfalse;return_neq_lt(rhs,lhs);}friendbooloperator>=(constM&lhs,constM&rhs){if(lhs==rhs)returntrue;return_neq_lt(rhs,lhs);}// a * 10^b (1 <= |a| < 10) の形で渡す// 相対誤差:10^{-16} ~ 10^{-19} 程度 (処理系依存)pair<longdouble,int>dfp()const{if(is_zero())return{0,0};intl=max<int>(0,_size()-3);intb=logD*l;stringprefix{};for(inti=_size()-1;i>=l;i--){prefix+=_itos(dat[i],i!=_size()-1);}b+=prefix.size()-1;longdoublea=0;for(auto&c:prefix)a=a*10.0+(c-'0');a*=tens.ten_ld(-((int)prefix.size())+1);a=clamp<longdouble>(a,1.0,nextafterl(10.0,1.0));if(neg)a=-a;return{a,b};}stringto_string()const{if(is_zero())return"0";stringres;if(neg)res.push_back('-');for(inti=_size()-1;i>=0;i--){res+=_itos(dat[i],i!=_size()-1);}returnres;}longdoubleto_ld()const{auto[a,b]=dfp();if(-tens.offset<=bandb<=tens.offset){returna*tens.ten_ld(b);}returna*powl(10,b);}longlongto_ll()const{longlongres=_to_ll(dat);returnneg?-res:res;}__int128_tto_i128()const{__int128_tres=_to_i128(dat);returnneg?-res:res;}friendistream&operator>>(istream&is,M&m){strings;is>>s;m=M{s};returnis;}friendostream&operator<<(ostream&os,constM&m){returnos<<m.to_string();}// 内部の関数をテストstaticvoid_test_private_function(constM&,constM&);private:// sizeint_size()const{returndat.size();}// a == bstaticbool_eq(constvector<int>&a,constvector<int>&b){returna==b;}// a < bstaticbool_lt(constvector<int>&a,constvector<int>&b){if(a.size()!=b.size())returna.size()<b.size();for(inti=a.size()-1;i>=0;i--){if(a[i]!=b[i])returna[i]<b[i];}returnfalse;}// a <= bstaticbool_leq(constvector<int>&a,constvector<int>&b){return_eq(a,b)||_lt(a,b);}// a < b (s.t. a != b)staticbool_neq_lt(constM&lhs,constM&rhs){assert(lhs!=rhs);if(lhs.neg!=rhs.neg)returnlhs.neg;boolf=_lt(lhs.dat,rhs.dat);if(f)return!lhs.neg;returnlhs.neg;}// a == 0staticbool_is_zero(constvector<int>&a){returna.empty();}// a == 1staticbool_is_one(constvector<int>&a){return(int)a.size()==1&&a[0]==1;}// 末尾 0 を削除staticvoid_shrink(vector<int>&a){while(a.size()&&a.back()==0)a.pop_back();}// 末尾 0 を削除void_shrink(){while(_size()&&dat.back()==0)dat.pop_back();}// a + bstaticvector<int>_add(constvector<int>&a,constvector<int>&b){vector<int>c(max(a.size(),b.size())+1);for(inti=0;i<(int)a.size();i++)c[i]+=a[i];for(inti=0;i<(int)b.size();i++)c[i]+=b[i];for(inti=0;i<(int)c.size()-1;i++){if(c[i]>=D)c[i]-=D,c[i+1]++;}_shrink(c);returnc;}// a - bstaticvector<int>_sub(constvector<int>&a,constvector<int>&b){assert(_leq(b,a));vector<int>c{a};intborrow=0;for(inti=0;i<(int)a.size();i++){if(i<(int)b.size())borrow+=b[i];c[i]-=borrow;borrow=0;if(c[i]<0)c[i]+=D,borrow=1;}assert(borrow==0);_shrink(c);returnc;}// a * b (fft)staticvector<int>_mul_fft(constvector<int>&a,constvector<int>&b){if(a.empty()||b.empty())return{};autom=ArbitraryNTT::multiply_u128(a,b);vector<int>c;c.reserve(m.size()+3);__uint128_tx=0;for(inti=0;;i++){if(i>=(int)m.size()&&x==0)break;if(i<(int)m.size())x+=m[i];c.push_back(x%D);x/=D;}_shrink(c);returnc;}// a * b (naive)staticvector<int>_mul_naive(constvector<int>&a,constvector<int>&b){if(a.empty()||b.empty())return{};vector<longlong>prod(a.size()+b.size()-1+1);for(inti=0;i<(int)a.size();i++){for(intj=0;j<(int)b.size();j++){longlongp=1LL*a[i]*b[j];prod[i+j]+=p;if(prod[i+j]>=(4LL*D*D)){prod[i+j]-=4LL*D*D;prod[i+j+1]+=4LL*D;}}}vector<int>c(prod.size()+1);longlongx=0;inti=0;for(;i<(int)prod.size();i++)x+=prod[i],c[i]=x%D,x/=D;while(x)c[i]=x%D,x/=D,i++;_shrink(c);returnc;}// a * bstaticvector<int>_mul(constvector<int>&a,constvector<int>&b){if(_is_zero(a)||_is_zero(b))return{};if(_is_one(a))returnb;if(_is_one(b))returna;if(min<int>(a.size(),b.size())<=128){returna.size()<b.size()?_mul_naive(b,a):_mul_naive(a,b);}return_mul_fft(a,b);}// 0 <= A < 1e18, 1 <= B < 1e9staticpair<vector<int>,vector<int>>_divmod_li(constvector<int>&a,constvector<int>&b){assert(0<=(int)a.size()&&(int)a.size()<=2);assert((int)b.size()==1);longlongva=_to_ll(a);intvb=b[0];return{_integer_to_vec(va/vb),_integer_to_vec(va%vb)};}// 0 <= A < 1e18, 1 <= B < 1e18staticpair<vector<int>,vector<int>>_divmod_ll(constvector<int>&a,constvector<int>&b){assert(0<=(int)a.size()&&(int)a.size()<=2);assert(1<=(int)b.size()&&(int)b.size()<=2);longlongva=_to_ll(a),vb=_to_ll(b);return{_integer_to_vec(va/vb),_integer_to_vec(va%vb)};}// 1 <= B < 1e9staticpair<vector<int>,vector<int>>_divmod_1e9(constvector<int>&a,constvector<int>&b){assert((int)b.size()==1);if(b[0]==1)return{a,{}};if((int)a.size()<=2)return_divmod_li(a,b);vector<int>quo(a.size());longlongd=0;intb0=b[0];for(inti=a.size()-1;i>=0;i--){d=d*D+a[i];assert(d<1LL*D*b0);intq=d/b0,r=d%b0;quo[i]=q,d=r;}_shrink(quo);return{quo,d?vector<int>{int(d)}:vector<int>{}};}// 0 <= A, 1 <= Bstaticpair<vector<int>,vector<int>>_divmod_naive(constvector<int>&a,constvector<int>&b){if(_is_zero(b)){cerr<<"Divide by Zero Exception"<<endl;exit(1);}assert(1<=(int)b.size());if((int)b.size()==1)return_divmod_1e9(a,b);if(max<int>(a.size(),b.size())<=2)return_divmod_ll(a,b);if(_lt(a,b))return{{},a};// B >= 1e9, A >= Bintnorm=D/(b.back()+1);vector<int>x=_mul(a,{norm});vector<int>y=_mul(b,{norm});intyb=y.back();vector<int>quo(x.size()-y.size()+1);vector<int>rem(x.end()-y.size(),x.end());for(inti=quo.size()-1;i>=0;i--){if(rem.size()<y.size()){// do nothing}elseif(rem.size()==y.size()){if(_leq(y,rem)){quo[i]=1,rem=_sub(rem,y);}}else{assert(y.size()+1==rem.size());longlongrb=1LL*rem[rem.size()-1]*D+rem[rem.size()-2];intq=rb/yb;vector<int>yq=_mul(y,{q});// 真の商は q-2 以上 q+1 以下だが自信が無いので念のため while を回すwhile(_lt(rem,yq))q--,yq=_sub(yq,y);rem=_sub(rem,yq);while(_leq(y,rem))q++,rem=_sub(rem,y);quo[i]=q;}if(i)rem.insert(begin(rem),x[i-1]);}_shrink(quo),_shrink(rem);auto[q2,r2]=_divmod_1e9(rem,{norm});assert(_is_zero(r2));return{quo,q2};}// 0 <= A, 1 <= Bstaticpair<vector<int>,vector<int>>_divmod_dc(constvector<int>&a,constvector<int>&b);// 1 / a を 絶対誤差 B^{-deg} で求めるstaticvector<int>_calc_inv(constvector<int>&a,intdeg){assert(!a.empty()&&D/2<=a.back()anda.back()<D);intk=deg,c=a.size();while(k>64)k=(k+1)/2;vector<int>z(c+k+1);z.back()=1;z=_divmod_naive(z,a).first;while(k<deg){vector<int>s=_mul(z,z);s.insert(begin(s),0);intd=min(c,2*k+1);vector<int>t{end(a)-d,end(a)},u=_mul(s,t);u.erase(begin(u),begin(u)+d);vector<int>w(k+1),w2=_add(z,z);copy(begin(w2),end(w2),back_inserter(w));z=_sub(w,u);z.erase(begin(z));k*=2;}z.erase(begin(z),begin(z)+k-deg);returnz;}staticpair<vector<int>,vector<int>>_divmod_newton(constvector<int>&a,constvector<int>&b){if(_is_zero(b)){cerr<<"Divide by Zero Exception"<<endl;exit(1);}if((int)b.size()<=64)return_divmod_naive(a,b);if((int)a.size()-(int)b.size()<=64)return_divmod_naive(a,b);intnorm=D/(b.back()+1);vector<int>x=_mul(a,{norm});vector<int>y=_mul(b,{norm});ints=x.size(),t=y.size();intdeg=s-t+2;vector<int>z=_calc_inv(y,deg);vector<int>q=_mul(x,z);q.erase(begin(q),begin(q)+t+deg);vector<int>yq=_mul(y,{q});while(_lt(x,yq))q=_sub(q,{1}),yq=_sub(yq,y);vector<int>r=_sub(x,yq);while(_leq(y,r))q=_add(q,{1}),r=_sub(r,y);_shrink(q),_shrink(r);auto[q2,r2]=_divmod_1e9(r,{norm});assert(_is_zero(r2));return{q,q2};}// int -> string// 先頭かどうかに応じて zero padding するかを決めるstaticstring_itos(intx,boolzero_padding){assert(0<=x&&x<D);stringres;for(inti=0;i<logD;i++){res.push_back('0'+x%10),x/=10;}if(!zero_padding){while(res.size()&&res.back()=='0')res.pop_back();assert(!res.empty());}reverse(begin(res),end(res));returnres;}// convert ll to vectemplate<typenameI,enable_if_t<internal::is_broadly_integral_v<I>>*=nullptr>staticvector<int>_integer_to_vec(Ix){ifconstexpr(internal::is_broadly_signed_v<I>){assert(x>=0);}vector<int>res;while(x)res.push_back(x%D),x/=D;returnres;}staticlonglong_to_ll(constvector<int>&a){longlongres=0;for(inti=(int)a.size()-1;i>=0;i--)res=res*D+a[i];returnres;}static__int128_t_to_i128(constvector<int>&a){__int128_tres=0;for(inti=(int)a.size()-1;i>=0;i--)res=res*D+a[i];returnres;}staticvoid_dump(constvector<int>&a,strings=""){if(!s.empty())cerr<<s<<" : ";cerr<<"{ ";for(inti=0;i<(int)a.size();i++)cerr<<a[i]<<", ";cerr<<"}"<<endl;}};usingbigint=MultiPrecisionInteger;/**
* @brief 多倍長整数
*/#line 6 "verify/verify-yosupo-math/yosupo-addition-of-big-integers.test.cpp"
//#line 2 "misc/fastio.hpp"
#line 8 "misc/fastio.hpp"
usingnamespacestd;#line 12 "misc/fastio.hpp"
namespacefastio{staticconstexprintSZ=1<<17;staticconstexprintoffset=64;charinbuf[SZ],outbuf[SZ];intin_left=0,in_right=0,out_right=0;structPre{charnum[40000];constexprPre():num(){for(inti=0;i<10000;i++){intn=i;for(intj=3;j>=0;j--){num[i*4+j]=n%10+'0';n/=10;}}}}constexprpre;voidload(){intlen=in_right-in_left;memmove(inbuf,inbuf+in_left,len);in_right=len+fread(inbuf+len,1,SZ-len,stdin);in_left=0;}voidflush(){fwrite(outbuf,1,out_right,stdout);out_right=0;}voidskip_space(){if(in_left+offset>in_right)load();while(inbuf[in_left]<=' ')in_left++;}voidsingle_read(char&c){if(in_left+offset>in_right)load();skip_space();c=inbuf[in_left++];}voidsingle_read(string&S){skip_space();while(true){if(in_left==in_right)load();inti=in_left;for(;i!=in_right;i++){if(inbuf[i]<=' ')break;}copy(inbuf+in_left,inbuf+i,back_inserter(S));in_left=i;if(i!=in_right)break;}}template<typenameT,enable_if_t<internal::is_broadly_integral_v<T>>*=nullptr>voidsingle_read(T&x){if(in_left+offset>in_right)load();skip_space();charc=inbuf[in_left++];[[maybe_unused]]boolminus=false;ifconstexpr(internal::is_broadly_signed_v<T>){if(c=='-')minus=true,c=inbuf[in_left++];}x=0;while(c>='0'){x=x*10+(c&15);c=inbuf[in_left++];}ifconstexpr(internal::is_broadly_signed_v<T>){if(minus)x=-x;}}voidrd(){}template<typenameHead,typename...Tail>voidrd(Head&head,Tail&...tail){single_read(head);rd(tail...);}voidsingle_write(constchar&c){if(out_right>SZ-offset)flush();outbuf[out_right++]=c;}voidsingle_write(constbool&b){if(out_right>SZ-offset)flush();outbuf[out_right++]=b?'1':'0';}voidsingle_write(conststring&S){flush(),fwrite(S.data(),1,S.size(),stdout);}voidsingle_write(constchar*p){flush(),fwrite(p,1,strlen(p),stdout);}template<typenameT,enable_if_t<internal::is_broadly_integral_v<T>>*=nullptr>voidsingle_write(constT&_x){if(out_right>SZ-offset)flush();if(_x==0){outbuf[out_right++]='0';return;}Tx=_x;ifconstexpr(internal::is_broadly_signed_v<T>){if(x<0)outbuf[out_right++]='-',x=-x;}constexprintbuffer_size=sizeof(T)*10/4;charbuf[buffer_size];inti=buffer_size;while(x>=10000){i-=4;memcpy(buf+i,pre.num+(x%10000)*4,4);x/=10000;}if(x<100){if(x<10){outbuf[out_right]='0'+x;++out_right;}else{uint32_tq=(uint32_t(x)*205)>>11;uint32_tr=uint32_t(x)-q*10;outbuf[out_right]='0'+q;outbuf[out_right+1]='0'+r;out_right+=2;}}else{if(x<1000){memcpy(outbuf+out_right,pre.num+(x<<2)+1,3);out_right+=3;}else{memcpy(outbuf+out_right,pre.num+(x<<2),4);out_right+=4;}}memcpy(outbuf+out_right,buf+i,buffer_size-i);out_right+=buffer_size-i;}voidwt(){}template<typenameHead,typename...Tail>voidwt(constHead&head,constTail&...tail){single_write(head);wt(std::forward<constTail>(tail)...);}template<typename...Args>voidwtn(constArgs&...x){wt(std::forward<constArgs>(x)...);wt('\n');}structDummy{Dummy(){atexit(flush);}}dummy;}// namespace fastiousingfastio::rd;usingfastio::skip_space;usingfastio::wt;usingfastio::wtn;#line 8 "verify/verify-yosupo-math/yosupo-addition-of-big-integers.test.cpp"
usingnamespaceNyaan;voidq(){intt;rd(t);while(t--){stringbuf1,buf2;rd(buf1,buf2);biginta=buf1,b=buf2;wtn((a+b).to_string());}}voidNyaan::solve(){intt=1;// in(t);while(t--)q();}