//BISMILLAHIR RAHMANIR RAHEEM //ALLAH IS WATCHING ME // Shoeb Akibul Islam // Dept of ICE, NSTU #include #include #include #include #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define dua ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define i_love_u_huu dua long long t;cin >> t;while(t--) #define ses "\n" #define whp " " #define mxi 200003 #define mp make_pair #define pii pair #define pf printf #define sf scanf #define ff first #define sob(z) (z).begin(), (z).end() #define ss second #define pb push_back #define rep0(i,a,b) for(int i=a; i=b; i--) #define rep1in(i,a,b) for(int i=a; i>b; i--) #define repv(i,a) for(auto i=a.begin(); i!=a.end();++i) #define INF 0x3f3f3f3f #define CLR(a,b) memset(a,b,sizeof(a)); #define PI acos(-1) #define what_is(x) cerr< > ::iterator it; //vector >a; //memset(arr,0,sizeof(hg)); //priority_queue , greater > pq; /// string single character erase- /// s.erase(s.begin()+x); where s is st ring name /// ans x is index; /// transform(sl.begin(), sl.end(), sl.begin(), ::tolower); /// transform(su.begin(), su.end(), su.begin(), ::toupper); typedef long long v99; typedef unsigned long long ull; using namespace std; using namespace __gnu_pbds; v99 fx[4]= {1,-1,0,0}; v99 fy[4]= {0,0,1,-1}; v99 ox8[] = {0, 0, 1, 1, 1, -1, -1, -1}; v99 oy8[] = {1,-1, 1, -1, 0, 0, -1, 1}; bool sort2val(const pii &a,const pii &b) { if(a.second==b.second)return a.first T gcd(T a, T b) { return (b != 0 ? gcd(b, a%b) : a); } template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); } typedef tree< v99, null_type, less, rb_tree_tag,tree_order_statistics_node_update> ott; typedef tree,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset; /// find_by_order(k) – kth index a ki ache, pointer return korbe. /// order_of_key(x) – x kon position a ache , oita bole dibe /**bool prime[10000020];vectorprm; void SieveOfEratosthenes(v99 n) { for(v99 i=4;i<=n;i+=2)prime[i]=true; for (v99 p=3; p*p<=n; p+=2) { if (prime[p] == false) { /// Update all multiples of p for (v99 i=p*p; i<=n; i += 2*p) prime[i] = true; } } rep1(i,2,n)if(!prime[i])prm.push_back(i); }*/ bool isPowerOfTwo (v99 x) { /* First x in the below expression is for the case when x is 0 */ return x && (!(x&(x-1))); } v99 pw(v99 a, v99 b) { v99 ans = 1; for(v99 i = 1; i <= b; ++i) ans = (ans * a); return ans; } void vout(auto a) { for(auto i:a)cout< inline T bigmod(T n,T p,T m) { if(p==0)return 1; else if(p%2==0) { v99 val=bigmod(n,p/2,m); return (T)((val*val)%m); } else return (T)(((v99)n*(v99)bigmod(n,p-1,m))%m); } ///------------------------------------------------------------------------------------------------------- void solve() { /// code is here-> v99 n;cin>>n; string s="01"; if(n==0)cout<<1<