#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;             
        cout << s.find("RL") + 2 << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int mx = 0;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] >= mx) ans++;
        mx = max(mx, a[i]);
    }
    cout << ans << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
long long getOne(long long a, long long m)
{
    return m / a;
}
 
long long getTwo(long long a, long long b, long long m)
{
    return m / lcm(a, b);    
}
 
long long getThree(long long a, long long b, long long c, long long m)
{
    return m / lcm(lcm(a, b), c);
}
 
long long get(long long a, long long b, long long c, long long m)
{
    long long c1 = getOne(a, m);
    long long c2 = getTwo(a, b, m) + getTwo(a, c, m);
    long long c3 = getThree(a, b, c, m);
    return (c1 - c2 + c3) * 6 + (c2 - 2 * c3) * 3 + c3 * 2;
}
 
void solve()
{
    long long a, b, c, m;
    cin >> a >> b >> c >> m;                                                                      
    cout << get(a, b, c, m) << " " << get(b, a, c, m) << " " << get(c, a, b, m) << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--){
		int n, m;
		cin >> n >> m;
		vector<vector<int>> g(n);
		forn(i, m){
			int v, u;
			cin >> v >> u;
			--v, --u;
			g[v].push_back(u);
			g[u].push_back(v);
		}
		vector<int> clr(n, -1);
		int ans = 0;
		forn(i, n) if (clr[i] == -1){
			queue<int> q;
			q.push(i);
			clr[i] = 0;
			vector<int> cnt(2);
			bool ok = true;
			while (!q.empty()){
				int v = q.front();
				q.pop();
				++cnt[clr[v]];
				for (int u : g[v]){
					if (clr[u] == clr[v])
						ok = false;
					else if (clr[u] == -1){
						clr[u] = clr[v] ^ 1;
						q.push(u);
					}
				}
			}
			if (ok) ans += max(cnt[0], cnt[1]);
		}
		cout << ans << '\n';
	}
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
int f(int x)
{
    int res = 0;
    while(x != 0)
    {
        res += x % 10;
        x /= 10;
    }
    return res;
}
 
void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    if(n == 1)
    {
        cout << s << "\n";
        return;
    }
    vector<int> cnt(10);
    int sum_digits = 0;
    for(auto x : s) 
    {
        cnt[x - '0']++;
        sum_digits += x - '0';
    }
    for(int x = 1; x <= n * 9; x++)
    {
        int nx = x;
        string sx = to_string(nx);
        while(nx > 9)
        {
            nx = f(nx);
            sx += to_string(nx);    
        }
        //cout << x << " " << sx << endl;               
        vector<int> need_cnt(10);
        int sum_digits_x = 0;
        for(auto y : sx)
        {
            need_cnt[y - '0']++;
            sum_digits_x += y - '0';
        }
        bool can = true;
        for(int i = 0; i <= 9; i++)
            if(need_cnt[i] > cnt[i]) can = false;
        if(sum_digits - sum_digits_x != x)
            can = false;
        if(can)
        {
            string res = "";
            for(int i = 9; i >= 0; i--)
            {
                for(int j = 0; j < cnt[i] - need_cnt[i]; j++)
                    res.push_back(char('0' + i));
            }
            res += sx;
            cout << res << endl;
            return;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
const int MOD = 998'244'353;
 
int add(int a, int b) {
	a += b;
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return a * 1ll * b % MOD;
}
int binPow(int a, int k) {
	int ans = 1;
	while (k > 0) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}
 
int n, m;
vector<int> a, k;
 
inline bool read() {
	if(!(cin >> n >> m))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	k.resize(m);
	fore (i, 0, m)
		cin >> k[i];
	return true;
}
 
inline void solve() {
	vector<int> lf(n, -1), rg(n, n);
	vector<int> st;
	fore (i, 0, n) {
		while (!st.empty() && a[st.back()] > a[i])
			st.pop_back();
		if (!st.empty())
			lf[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; i--) {
		while (!st.empty() && a[st.back()] >= a[i])
			st.pop_back();
		if (!st.empty())
			rg[i] = st.back();
		st.push_back(i);
	}
 
	int commonSum = 0;
	vector<int> la(m + 1), lk(m + 1), ra(m + 1), rk(m + 1);
 
	//[l, r)
	auto addSeg = [](vector<int> &pS, int l, int r, int val) {
		pS[l] = add(pS[l], val);
		pS[r] = add(pS[r], -val);
	};
 
	fore (i, 0, n) {
		int cnt = mul(i - lf[i], rg[i] - i);
		int rem = add(mul(i + 1, n - i), -cnt);
		int ia = binPow(a[i], MOD - 2);
		commonSum = add(commonSum, mul(rem, ia));
 
		int p = lower_bound(k.begin(), k.end(), a[i]) - k.begin();
		addSeg(la, 0, p, mul(cnt, ia));
		addSeg(lk, 0, p, mul(cnt, ia));
		addSeg(ra, p, m, cnt);
		addSeg(rk, p, m, mul(cnt, add(2, -a[i])));
	}
	fore (i, 0, m) {
		la[i + 1] = add(la[i + 1], la[i]);
		lk[i + 1] = add(lk[i + 1], lk[i]);
		ra[i + 1] = add(ra[i + 1], ra[i]);
		rk[i + 1] = add(rk[i + 1], rk[i]);
	}
 
	fore (i, 0, m) {
		int ans = commonSum;
		ans = add(ans, mul(add(la[i], ra[i]), k[i]));
		ans = add(ans, add(lk[i], rk[i]));
		cout << ans << '\n';
	}
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
 
const int K = 301;
 
using mat = vector<vector<int>>;
 
int n, m, mod, k;
 
int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
 
int mul(int x, int y) {
  return x * 1LL * y % mod;
}
 
unsigned long long aux[K][K];
 
mat mul(mat a, mat b) {
  mat b2(k, vector<int>(k));
  forn(x, k) forn(y, k) b2[x][y] = b[y][x];
  mat c(k, vector<int>(k));
  forn(x, k) forn(y, k) {
    aux[x][y] = 0;
    forn(z, k) {
      aux[x][y] += a[x][z] * 1ll * b2[y][z];
      if((z & 15) == 15)
        aux[x][y] %= mod;
    }
    c[x][y] = aux[x][y] % mod;
  }
  return c;
}
 
mat binpow(mat a, int b) {
  mat c(k, vector<int>(k));
  forn(i, k) c[i][i] = 1;
  while (b) {
    if (b & 1) c = mul(c, a);
    a = mul(a, a);
    b >>= 1;
  }
  return c;
}
 
int main() {
  cin >> n >> m >> mod;
  k = 2 * m + 1;
  mat a(k, vector<int>(k));
  a[k - 1][k - 1] = 1;
  forn(i, m) forn(f, 2) {
    for (int l = f ? 0 : i; l <= i; ++l) {
      for (int r = i; r < m; ++r) {
        a[i * 2 + f][k - 1] = add(a[i * 2 + f][k - 1], 1);
        for (int j = l; j <= r; ++j) {
          a[i * 2 + f][j * 2 + (j == l)] = add(a[i * 2 + f][j * 2 + (j == l)], 1);
        }
      }
    }
  }
  auto res = binpow(a, n);
  cout << res[1][k - 1] << endl;
}

t = int(input())
for i in range(t):
    n, m, d = map(int, input().split())
    k = 1 + d // m
    print((n + k - 1) // k)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		int sum = 0;
		vector<int> a;
		for (int i = 0; i < int(s.size()); ++i) {
			int x = s[i] - '0';
			sum += x;
			a.push_back(x - (i == 0));
		}
		sort(a.begin(), a.end());
		int ans = 0;
		while (sum > 9) {
			sum -= a.back();
			a.pop_back();
			++ans;
		}
		cout << ans << '\n';
	}
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
bool get(int x, int a, int lim){
	int f = 0;
	for (int i = 59; i >= 0; i--){
		f <<= 1;
		if (((x >> i) & 1) == 1){
			f++;
		} 
		if (((a >> i) & 1) == 1){
			f -= min(lim, f);
		}
	}
	return (f == 0);
}
 
void solve(){
	int x, a;
	cin >> x >> a;
 
	if (!get(x, a, 1ll << 60)){
		cout << -1 << '\n';
		return;
	}
 
	int l = 0, r = (1ll << 60);
	while(l <= r){
		int m = l + (r - l) / 2;
		if (get(x, a, m)){
			r = m - 1;
		}
		else{
			l = m + 1;
		}
	}
 
	cout << l << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	for (int test = 0; test < tests; test++){
		solve();
	}
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	
	for (int test = 0; test < t; test++){
    	int n, m;
    	cin >> n >> m;
    
    	vector<int> a(n), b(m);
    	for (int i = 0; i < n; i++){
    		cin >> a[i];
    	}
    	for (int i = 0; i < m; i++){
    		cin >> b[i];
    	}
    
    	int max_a = n + m + 1;
    
    	vector<int> cnt_b(max_a, 0), cnt_a(max_a, 0);
    
    	for (int i = 0; i < n; i++){
    		cnt_a[a[i]]++;
    	}
    
    	for (int i = 0; i < m; i++){
    		cnt_b[b[i]]++;
    	}
    
    	vector<int> cnt_del(max_a, 0);
    
    	int f = 0, s = 0, com = 0;
    
    	for (int i = 1; i < max_a; i++){
    		for (int j = i; j < max_a; j += i){
    			cnt_del[j] += cnt_a[i];
    		}
    	}
    
    	for (int i = 1; i < max_a; i++){
    		if (cnt_b[i] == 0){
    			continue;
    		}
    
    		if (cnt_del[i] == 0){
    			s += cnt_b[i];
    		}
    		else if (cnt_del[i] == n){
    			f += cnt_b[i];
    		}
    	}
    
    	com = m - f - s;
    
    	bool turn = 0;
    	string win = "";
    
    	while(1){
    		if (turn == 0){
    			if (com > 0){
    				com--;
    			}
    			else if (f > 0){
    				f--;
    			}
    			else{
    				win = "Bob";
    				break;
    			}
    		}
    		else{
    			if (com > 0){
    				com--;
    			}
    			else if (s > 0){
    				s--;
    			}
    			else{
    				win = "Alice";
    				break;
    			}
    		}
    		turn = !turn;
    	}
    
    	cout << win << '\n';
	}
 
    return 0; 
}

#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int MOD = 998244353;
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m;
	cin >> m;
	vector<long long> a(m);
	forn(i, m) cin >> a[i];
	auto xs = a;
	sort(xs.begin(), xs.end());
	for (auto& x : a) x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
 
	vector<long long> f(m);
 
	auto upd = [&](int x, long long val){
		for (int i = x; i < int(f.size()); i |= i + 1)
			f[i] += val;
	};
	auto get = [&](int x){
		long long sum = 0;
		for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
			sum += f[i];
		return sum;
	};
 
	long long sum = 0;
	ordered_set<int> cur;
	for (int x : a){
		cur.insert(x);
		int n = cur.size();
		sum += xs[x];
		upd(x, xs[x]);
 
		if (n < 3) continue;
 
		auto getL = [&](int pos, auto it){
			if (it == cur.begin()) return 0ll;
			return xs[*prev(it)] * 1ll * pos - get(*it - 1);
		};
 
		auto getR = [&](int pos, auto it){
			if (next(it) == cur.end()) return 0ll;
			return (sum - get(*it)) - xs[*next(it)] * 1ll * (n - pos - 1);
		};
 
		int l = 0, r = n - 1;
		int pos = n;
		while (l <= r){
			int m = (l + r) / 2;
			auto it = cur.find_by_order(m);
			if (getL(m, it) >= getR(m, it)){
				pos = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
 
		long long ans = 1e18;
		forn(_, 2){
			if (0 <= pos && pos < n){
				auto it = cur.find_by_order(pos);
				ans = min(ans, max(getL(pos, it), getR(pos, it)));
			}
			--pos;
		}
 
		cout << mul(ans % MOD, binpow(n - 2, MOD - 2)) << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const long long INF64 = 1e18;
const int MOD = 998244353;
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m;
	cin >> m;
	vector<long long> a(m);
	int n = m + 2;
	forn(i, m) cin >> a[i];
 
	int p = sqrt(n) + 3;
	auto xs = a;
	xs.push_back(0);
	sort(xs.begin(), xs.end());
	xs.push_back(xs.back() + 1);
	vector<int> cntbl(n), rgh(n, -1);
	rgh[0] = 0;
	rgh[(n - 1) / p] = n - 1;
	vector<long long> sumbl(n);
	vector<int> cll(n, 0), clr(n, n - 1);
 
	set<int> on({0, n - 1});
	int cnt = 0;
	long long sum = 0;
	forn(i, m){
		int x = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
		int bl = x / p;
 
		++cntbl[bl];
		sumbl[bl] += xs[x];
		rgh[bl] = max(rgh[bl], x);
		sum += xs[x];
		++cnt;
 
		auto it = on.lower_bound(x);
		clr[x] = *it;
		cll[x] = *prev(it);
		clr[*prev(it)] = cll[*it] = x;
		on.insert(x);
 
		if (cnt < 3) continue;
 
		int lst = clr[0];
		int cntl = 0;
		long long suml = 0;
 
		auto getL = [&](int x){ return xs[cll[x]] * 1ll * cntl - suml; };
		auto getR = [&](int x){ return (sum - suml - xs[x]) - xs[clr[x]] * 1ll * (cnt - cntl - 1); };
		auto check = [&](int x){
			if (x == 0) return true;
			if (x == n - 1) return false;
			return getL(x) < getR(x);
		};
 
		while (lst < n - 1){
			int bl = lst / p;
			assert(rgh[bl] != -1);
			if (!check(rgh[bl])) break;
			cntl += cntbl[bl];
			suml += sumbl[bl];
			lst = clr[rgh[bl]];
		}
 
		while (lst < n - 1){
			if (!check(lst)) break;
			++cntl;
			suml += xs[lst];
			lst = clr[lst];
		}
 
		x = lst;
		long long ans = 1e18;
		if (x != n - 1)
			ans = min(ans, max(getL(x), getR(x)));
		assert(x != 0);
		x = cll[x];
		if (x != 0){
			--cntl;
			suml -= xs[x];
			ans = min(ans, max(getL(x), getR(x)));
		}
 
		cout << mul(ans % MOD, binpow(cnt - 2, MOD - 2)) << '\n';
	}
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
vector<long long> ans;
int n;
vector<int> cnt;
 
void prepare_aux(int l, int r, vector<int>& a)
{
    if(l > r) return;
    int m = (l + r) / 2;
    a[m] = r - l + 1;
    if(l < m) prepare_aux(l, m - 1, a);
    if(m < r) prepare_aux(m + 1, r, a);
}
 
vector<int> prepare(int len)
{
    vector<int> a(len);
    prepare_aux(0, len - 1, a);
    return a;    
}
 
int get_left(int len)
{
    int m = (len - 1) / 2;
    return m;
}
 
int get_right(int len)
{
    int m = (len - 1) / 2;
    return len - m - 1;
}
 
vector<long long> get(int x)
{
    vector<long long> res(x + 1);
    int m = (x - 1) / 2;
    int left = m;
    int right = x - m - 1;
    vector<int> prepared = prepare(x);
    //cout << x << endl;
    // swap m with something to the left
    {
        for(int i = 0; i < m; i++)
        {
            int lost = abs(m - i);
            //cout << i << " " << m << " " << lost << endl;
            res[lost]++;  
        }
    }
    // swap m with something to the right
    {
        for(int i = 0; i < right; i++)
        {
            int lost = i + 1;
            //cout << m << " " << i + m + 1 << " " << lost << endl;
            res[lost]++;
        }
    }
    // swap something to the left with something to the right
    {
        map<int, int> lost_left;
        map<int, int> lost_right;
        for(int i = 0; i < x; i++)
        {
            if(i == m) continue;
            if(i < m)
            {
                int lost = get_right(prepared[i]) + 1;
                lost_left[lost]++; 
            }
            else
            {
                int lost = get_left(prepared[i]) + 1;
                lost_right[lost]++;
            }
        }
        for(auto p : lost_left)
            for(auto p2 : lost_right)
            {
                //cerr << p.first << " " << p.second << endl;
                //cerr << p2.first << " " << p2.second << endl;
                res[p.first + p2.first] += p.second * 1ll * p2.second;
            }
    }
    //cout << x << ":";
    //for(auto y : dp[x]) cout << " " << y;
    //cout << endl;
    return res;
}                    
 
void calc(int l, int r)
{
    if(l > r) return;
    int m = (l + r) / 2;
    if(l < m) calc(l, m - 1);
    if(m < r) calc(m + 1, r);
    int len = r - l + 1;
    cnt[len]++;            
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;         
    ans.resize(n + 1);
    cnt.resize(n + 1);
    calc(0, n - 1);
    for(int i = 1; i <= n; i++)
        if(cnt[i] != 0)
        {
            auto g = get(i);
            for(int j = 0; j <= i; j++)
                ans[n - j] += cnt[i] * g[j];
        }
    for(auto x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

t = int(input())
for i in range(t):
    n = int(input())
    s = input()
    if '2025' in s and not '2026' in s:
        print(1)
    else:
        print(0)

t = int(input())
for i in range(t):
    a, b = map(int, input().split())
    if a < b:
        a, b = b, a
    x, y = 0, 0
    ans = 0
    cur = 1
    while True:
        x, y = y + cur, x
        if x <= a and y <= b:
            ans += 1
            cur *= 2
        else:
            break
    print(ans)

def good(x, y, n, k):
    ans = True
    for i in range(n):
        if x[i] <= y[(i + k) % n]:
            ans = False
    return ans     
 
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    k1, k2 = 0, 0
    for i in range(n):
        if good(b, a, n, i):
            k1 += 1
        if good(c, b, n, i):
            k2 += 1
    print(k1 * k2 * n)

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 55;
const int MOD = 998244353;
 
int mul(int x, int y) {
  return x * 1LL * y % MOD;
}
 
int binpow(int x, int y) {
  int z = 1;
  while (y > 0) {
    if (y & 1) z = mul(z, x);
    x = mul(x, x);
    y >>= 1;
  }
  return z;
}
 
int main() {
  vector<int> f(N, 1);
  for (int i = 1; i < N; ++i)
    f[i] = (f[i - 1] * 1LL * i) % MOD;
 
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int &x : a) cin >> x;
    int k = accumulate(a.begin(), a.end(), 0) / n;
    int z = 0, bad = 0;
    for (int i = 1; i <= n; ++i) {
      int x = min(a[i], k);
      a[i] -= x;
      a[0] -= k - x;
      z += a[i] == 0;
      bad |= a[i] > 1 || a[0] < 0;
    }
    bad |= a[0] > z;
    int ans = bad ? 0 : f[z];
    if (!bad) {
      ans = mul(ans, f[n - z + a[0]]);
      ans = mul(ans, binpow(f[a[0]], MOD - 2));
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
  int n, m;
  long long k;
  cin >> n >> m >> k;
  vector<vector<int>> ev(m);
  for (int i = 0; i < m; ++i) {
    int x; cin >> x;
    ev[x - 1].push_back(-1);
  }
  for (int i = 0; i < n; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    ev[x - 1].push_back(z - y);
    k -= y;
  }
  int ans = 0;
  multiset<int> s;
  for (int i = 0; i < m; ++i) {
    reverse(ev[i].begin(), ev[i].end());
    for (int x : ev[i]) {
      if (x == -1) {
        if (!s.empty()) {
          s.erase(--s.end());
          ++ans;
        }
      } else {
        s.insert(x);
      }
    }
  }
  while (!s.empty() && *s.begin() <= k) {
    k -= *s.begin();
    s.erase(s.begin());
    ++ans;
  }
  cout << ans << '\n';
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int LOGN = 61;
 
int add(int x, int y)
{
    x += y;
    if(x >= MOD) x -= MOD;
    if(x < 0) x += MOD;
    return x;
}
 
int sub(int x, int y)
{
    return add(x, -y);
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}   
 
int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}                   
 
vector<int> get_required(long long x)
{
    vector<int> ans(LOGN);
    int cnt = 0;
    for(int i = LOGN - 1; i >= 0; i--)
    {
        if((x >> i) & 1)
        {
            ans[i + cnt]++;
            cnt++;
        }
    }
    return ans;
}
 
void solve()
{
    int n, m;
    cin >> n >> m;        
    vector<int> freq(LOGN);
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        freq[x]++;
    }
    
    int max_n = n + m + 111;
 
    vector<int> fact(max_n, 1);
    for(int i = 1; i < max_n; i++)
        fact[i] = mul(fact[i - 1], i);
    vector<int> inv_fact(max_n);
    for(int i = 0; i < max_n; i++)
        inv_fact[i] = binpow(fact[i], MOD - 2);
    vector<int> pow2(max_n, 1);
    for(int i = 1; i < max_n; i++)
        pow2[i] = mul(pow2[i - 1], 2);
 
    auto choose = [&](int x, int y)
    {           
        if(x < y || x < 0 || y < 0) return 0;
        return mul(fact[x], mul(inv_fact[y], inv_fact[x - y]));
    };
 
    auto sum_greater = [&](int x, int y)
    {
        if(y >= x) return 0;
        int ans = pow2[x];
        for(int i = 0; i <= y; i++)
            ans = sub(ans, choose(x, i));
        return ans;
    };
 
    for(int i = 0; i < m; i++)
    {
        int t;
        long long x;
        cin >> t >> x;
        if(t == 1)
            freq[x]++;
        else if(t == 2)
            freq[x]--;
        else
        {
            auto req = get_required(x);
            int ans = 0;
            int cur = 1;
            int cnt_less = 0;
            for(int i = 0; i < LOGN; i++) cnt_less += freq[i];
            for(int i = LOGN - 1; i >= 0; i--)
            {
                cnt_less -= freq[i];
                ans = add(ans, mul(cur, mul(sum_greater(freq[i], req[i]), pow2[cnt_less])));
                cur = mul(cur, choose(freq[i], req[i]));
            }
            ans = add(ans, cur);
            cout << ans << "\n";
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    int t = 1;
    //cin >> t;
    for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int MOD = 998244353;
 
int add(int a, int b){
    a += b;
    if (a >= MOD) a -= MOD;
    if (a < 0) a += MOD;
    return a;
}
 
int mul(int a, int b){
    return a * 1ll * b % MOD;
}
 
int binpow(int a, int b){
    int res = 1;
    while (b){
        if (b & 1)
            res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}
 
int n, k;
vector<vector<int>> g;
 
struct dpar{
    vector<int> dp;
    int ml, ad;
    dpar(){
        ml = 1, ad = 0;
        dp.clear();
    }
    int& operator [](int k){
        return dp[max(0, int(dp.size()) - k - 1)];
    }
    int get(int k){
        int x = dp[max(0, int(dp.size()) - k - 1)];
        return add(mul(x, ml), ad);
    }
};
 
vector<dpar> dp;
vector<int> fact;
 
void dfs(int v){
    int bst = -1;
    vector<int> val;
    for (int u : g[v]){
        dfs(u);
        dp[u].dp.push_back(add(0, mul(binpow(dp[u].ml, MOD - 2), -dp[u].ad)));
        if (bst == -1 || dp[u].dp.size() > dp[bst].dp.size())
            bst = u;
        val.push_back(dp[u].get(k - 1));
    }
    if (val.empty()){
        dp[v].dp.push_back(1);
        return;
    }
 
    vector<int> pr(val.size() + 1, 1), su(val.size() + 1, 1);
    forn(i, val.size()){
        pr[i + 1] = mul(pr[i], val[i]);
        su[val.size() - i - 1] = mul(su[val.size() - i], val[val.size() - i - 1]);
    }
 
    swap(dp[v], dp[bst]);
    {
        int i = find(g[v].begin(), g[v].end(), bst) - g[v].begin();
        int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1]));
        if (cur == 0){
            int mx = 1;
            for (int u : g[v]) mx = max(mx, int(dp[u].dp.size()));
            dp[v].dp.assign(mx, 0);
            dp[v].ml = 1, dp[v].ad = 0;
        }
        else{
            dp[v].ml = mul(dp[v].ml, cur);
            dp[v].ad = mul(dp[v].ad, cur);
        }
    }
 
    int rev = binpow(dp[v].ml, MOD - 2);
    forn(i, g[v].size()){
        int u = g[v][i];
        if (u == bst) continue;
        int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1]));
        int tot = mul(cur, dp[u].get(n));
        dp[v].ad = add(dp[v].ad, tot);
        forn(j, dp[u].dp.size()){
            dp[v][j] = add(dp[v][j], -mul(rev, tot));
            dp[v][j] = add(dp[v][j], mul(mul(cur, dp[u].get(j)), rev));
        }
    }
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--){
        cin >> n >> k;
        g.assign(n, {});
        for (int i = 1; i < n; ++i){
            int p;
            cin >> p;
            --p;
            g[p].push_back(i);
        }
        dp.assign(n, {});
        fact.resize(n + 1, 1);
        for (int i = 1; i <= n; ++i)
            fact[i] = mul(fact[i - 1], i);
        dfs(0);
        cout << dp[0].get(n) << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        auto get = [&](int x, int y) {
            if (x >= 0 && x < n && y >= 0 && y < n) return x * n + y + 1;
            return 0;
        };
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int cur = get(i, j);
                for (int d = 0; d < 4; ++d) cur += get(i + dx[d], j + dy[d]);
                ans = max(ans, cur);
            }
        }
        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 1;
    if (n == 2) ans = 9;
    else if (n == 3 || n == 4) ans = 4 * n * n - n - 4;
    else if (n > 4) ans = 5 * n * n - 5 * n - 5;
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
 
    int sum = 0;
    int cnt_one = 0;
 
    for (int i = 0; i < n; i++){
        if (a[i] > 0){
            cnt_one++;
        }
        sum += a[i];
    }
 
    int sum2 = sum - cnt_one;
    int sub = n - 1 - sum2;
 
    cout << cnt_one - max(0ll, sub) << '\n';
}
 
signed main()
{
#ifdef FELIX
    auto _clock_start = chrono::high_resolution_clock::now();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
#ifdef FELIX
    cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
        chrono::high_resolution_clock::now()
            - _clock_start).count() << "ms." << endl;
#endif
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
typedef long long li;
 
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    fore(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
inline void solve() {
    int n; li k;
    cin >> n >> k;
    vector<int> q(n), r(n);
    fore (i, 0, n)
        cin >> q[i];
    fore (i, 0, n)
        cin >> r[i];
    
    sort(q.begin(), q.end());
    sort(r.begin(), r.end());
 
    auto check = [&](int cnt) {
        fore (i, 0, cnt) {
            if (li(q[i] + 1) * (r[cnt - 1 - i] + 1) - 1 > k)
                return false;
        }
        return true;
    };
 
    int lf = 0, rg = n + 1;
    while (rg - lf > 1) {
        int mid = (lf + rg) >> 1;
        if (check(mid))
            lf = mid;
        else
            rg = mid;
    }
    cout << lf << endl;
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int t = 1; cin >> t;
    while (t--) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int cost(char c)
{
    if(c == 'I') return 1;
    return 5;
}

int eval(string s)
{
    int n = s.size();
    int ans = 0;
    for(int i = 0; i < n; i++)
        if(s[i] == 'I' && i + 1 < n && s[i + 1] == 'V')
            ans--;
        else ans += cost(s[i]);
    return ans;    
}

void solve()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'X')
        {
            s[i] = 'V';
            ans += 5;
        }
    }
    int inc = 0;
    int same = 0;
    int qcount = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] != '?') continue;
        int r = i;
        while(r < n && s[r] == '?') r++;
        int len = r - i;
        if(i > 0 && s[i - 1] == 'I') len++;
        if(r < n && s[r] == 'V') 
        {
            inc--;
            len++;
        }
        inc += len / 2;
        same += len % 2;
        qcount += (r - i);
        i = r - 1;        
    }
    for(int i = 0; i < n; i++)
        if(s[i] == '?') s[i] = 'I';
    ans += eval(s);
    for(int i = 0; i < q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int used_v = max(0, min(b, qcount - c));
        int used_x = max(0, qcount - c - b);
        int cur = ans;
        cur += used_v * 4 + used_x * 9;
        int rep = used_v + used_x;
        cur -= min(inc, rep) * 2;
        rep -= (inc + same);
        cur += max(0, rep) * 2;
        cout << cur << "\n";  
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e9;
const int MOD = 998244353;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> max_left(n + 1, -1);
    for(int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        max_left[r] = max(max_left[r], l);
    }
    for(int i = 1; i <= n; i++)
        max_left[i] = max(max_left[i], max_left[i - 1]);
    vector<int> dp(n + 1);
    vector<int> prefsum(n + 2);
    dp[0] = 2;
    prefsum[1] = 2;
    for(int i = 1; i <= n; i++)
    {
        int j = max_left[i - 1] + 1;
        dp[i] = add(prefsum[i], -prefsum[j]);
        prefsum[i + 1] = add(prefsum[i], dp[i]);
    }
    cout << dp[n] << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int B = 13;
const int M = (1 << (B - 1));
const int INF = 1e9;
 
int dp[B][M];
 
void upd(int& a, int b)
{
    if(a < b) a = b;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> id(n);
    int q;
    cin >> q;
    vector<int> l(q), x(q);
    for(int i = 0; i < q; i++)
    {
        int r;
        cin >> l[i] >> r >> x[i];
        --l[i];
        --r;
        id[r].push_back(i);
    }
    
    for(int i = 0; i < B; i++)
        for(int j = 0; j < M; j++)
            dp[i][j] = -INF;
    dp[0][0] = INF;
    vector<int> ans(q, 0);
    for(int i = 0; i < n; i++)
    {
        int val = a[i];
        upd(dp[1][val], i);
        for(int j = 1; j < B - 1; j++)
        {
            for(int k = 1; k < M; k++)
            {
                upd(dp[j + 1][k ^ val], dp[j][k]);
            }
        }
        for(auto qr : id[i])
        {
            int cur = x[qr];
            for(int j = B - 1; j >= 0; j--)
                if(dp[j][cur] >= l[qr])
                    ans[qr] = j;
        }
    }
    
    for(int i = 0; i < q; i++)
        cout << ans[i] << " ";
    cout << endl;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n, a;
        cin >> n >> a;
        vector <int> v(n);
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            if (a > v[i]) ++l;
            if (a < v[i]) ++r;
        }
        
        cout << (l > r ? a - 1 : a + 1) << endl;
    }
    return 0;
}

for _ in range(int(input())):
    s = input()
    for i in range(len(s) - 1):
        if s[i] != '<' and s[i + 1] != '>':
            print(-1)
            break
    else:
        print(len(s) - min(s.count('<'), s.count('>')))

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    li s = 0, mn = 0, bst = 0;
    for (int i = 0; i < n; ++i) {
      int x;
      cin >> x;
      s += x;
      li cur = (i + 1) * li(i + 2) - s;
      mn = min(mn, cur);
      bst = max(bst, cur - mn);
    }
    cout << s + bst << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const long long INF = 1000000000000LL + 1;

void solve(){
    int x;
    long long y, k;
 
    cin >> x >> y >> k;
 
    long long l = 1, r = INF;
    long long m;
 
    while(l <= r){
        m = l + (r - l) / 2;
        long long ost = (m - 1);
        for (int i = 0; i < x; i++){
            ost -= ost / y;
        }
        if (ost + 1 > k){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
 
    if (r == INF){
        cout << -1 << '\n';
    }
    else{
        cout << r << '\n';
    }
}
 
signed main()
{
#ifdef FELIX
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
 
  int t = 1;
  cin >> t;
  while(t--){
    solve();
  }
 
#ifdef FELIX
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    chrono::high_resolution_clock::now()
      - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int INF = 1'000'000'000'000LL;
 
void solve(){
  int x, y, k;
  cin >> x >> y >> k;
 
  if (y == 1){
    cout << -1 << '\n';
    return;
  }
 
  for (int i = 0; i < x; ){
    int cur = (k - 1) / (y - 1);
    if (cur == 0){
      break;
    }
    int fk = (cur + 1) * (y - 1) + 1;
    int cnt = (fk - k + cur - 1) / cur;
    cnt = min(x - i, cnt);
    k += cnt * cur;
    if (k > INF){
      cout << -1 << '\n';
      return;
    } 
    i += cnt;
  }
 
  cout << k << '\n';
}
 
signed main()
{
#ifdef FELIX
    auto _clock_start = chrono::high_resolution_clock::now();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
#ifdef FELIX
    cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
        chrono::high_resolution_clock::now()
            - _clock_start).count() << "ms." << endl;
#endif
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
typedef long long li;
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
int n;
vector<li> x[3];
 
bool read() {
    if(!(cin >> n))
        return false;
    fore (k, 0, 3) {
        x[k].resize(n);
        fore (i, 0, n)
            cin >> x[k][i];
    }
    return true;
}
 
void solve() {
    vector< vector<li> > w(n, vector<li>(1 << 4, 0));
    fore (i, 0, n) {
        fore (mask, 0, 1 << 4) {
            fore (k, 0, 4) if ((mask >> k) & 1)
                w[i][mask] += x[k & 1][i] * (k < 2 ? -1 : 1);
        }
    }
 
    vector< vector<li> > d(n + 1, vector<li>(1 << 4, -INF64));
    d[0][0] = 0;
    fore (i, 0, n) fore (mask, 0, 1 << 4) {
        if (d[i][mask] < -INF64 / 2)
            continue;
        
        d[i + 1][mask] = max(d[i + 1][mask], d[i][mask] + x[2][i]);
 
        int filter = ((1 << 4) - 1) ^ mask;
        for (int cmask = filter; cmask > 0; cmask = (cmask - 1) & filter)
            d[i + 1][mask | cmask] = max(d[i + 1][mask | cmask], d[i][mask] + 2ll * w[i][cmask]);
    }
    cout << d[n][(1 << 4) - 1] << endl;
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
const int LOGN = 19;
const int MOD = 998244353;
int g = 3;
 
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}
int norm(int a) {
    while(a >= MOD) a -= MOD;
    while(a < 0) a += MOD;
    return a;
}
int binPow (int a, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1) {
        if (k & 1)
            ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}
int inv(int a) {
    return binPow(a, MOD - 2);
}
 
vector<int> w[LOGN], rv;
bool precalced = false;
 
void precalc() {
    if(precalced)
        return;
    precalced = true;
    
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    fore(st, 0, LOGN) {
        w[st].assign(1 << st, 1);
 
        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int cw = 1;
 
        fore(k, 0, (1 << st)) {
            w[st][k] = cw;
            cw = mul(cw, bw);
        }
    }
    
    rv.assign(1 << LOGN, 0);
    fore(i, 1, sz(rv))
        rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}
 
const int MX = (1 << LOGN) + 3;
 
inline void fft(int a[MX], int n, bool inverse) {
    precalc();
    
    int ln = __builtin_ctz(n);
    assert((1 << ln) < MX);
    assert((1 << ln) == n);
 
    fore(i, 0, n) {
        int ni = rv[i] >> (LOGN - ln);
        if(i < ni) swap(a[i], a[ni]);
    }
 
    for(int st = 0; (1 << st) < n; st++) {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) {
            fore(pos, k, k + len) {
                int l = a[pos];
                int r = mul(a[pos + len], w[st][pos - k]);
 
                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }
    
    if(inverse) {
        int in = inv(n);
        fore(i, 0, n)
            a[i] = mul(a[i], in);
        reverse(a + 1, a + n);
    }
}
 
int aa[MX], bb[MX], cc[MX];
 
vector<int> multiply(const vector<int> &a, const vector<int> &b, int cutoff) {
    int ln = 1;
    while(ln < (sz(a) + sz(b)))
        ln <<= 1;
    
    fore(i, 0, ln)
        aa[i] = (i < sz(a) ? a[i] : 0);
    fore(i, 0, ln)
        bb[i] = (i < sz(b) ? b[i] : 0);
        
    fft(aa, ln, false);
    fft(bb, ln, false);
    
    fore(i, 0, ln)
        cc[i] = mul(aa[i], bb[i]);
    fft(cc, ln, true);
    
    vector<int> ans(cc, cc + ln);
    while((ans.size() > 0 && ans.back() == 0) || ans.size() > cutoff)
        ans.pop_back();
    return ans;
}
 
vector<int> fact, ifact;
 
void precalc_factorials(int s) {
    fact.resize(s);
    fact[0] = 1;
    for(int i = 1; i < s; i++)
        fact[i] = mul(fact[i - 1], i);
    ifact.resize(s);
    for(int i = 0; i < s; i++)
        ifact[i] = inv(fact[i]);
}
 
int choose(int n, int k) {
    if(n < 0 || n < k || k < 0) return 0;
    return mul(fact[n], mul(ifact[n - k], ifact[k]));
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> lens(k);
    for(int i = 0; i < k; i++) cin >> lens[i];
 
    int cutoff = n + 1;
    precalc_factorials(1 << LOGN);
    vector<int> segments(6);
    segments[0] = 1;
    for(auto len : lens)
        for(int i = 1; i <= len; i++)
            segments[i]++;
    vector<vector<int>> poly(6);
    for(int i = 0; i < 6; i++) {
        if(segments[i] == 0)
            poly[i] = { 1 };
        else {
            int choices = norm(m - i);
            int p = 1;
            poly[i].resize(cutoff);
            for(int k = 0; k < cutoff; k++) {
                int cur = mul(p, choose(k + segments[i] - 1, k));
                poly[i][k] = cur;
                p = mul(p, choices);
            }
        }
    }
    vector<int> ans = { 1 };
    for(int i = 0; i < 6; i++)
        ans = multiply(ans, poly[i], cutoff);
 
    int used = 0;
    int coef = 1;
    for(auto len : lens) {
        coef = mul(coef, fact[len]);
        used += len;
    }
    int res = mul(coef, ans[n - used]);
    cout << res << endl;
}

#include <iostream>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        cout << (3 - n % 3) % 3 << endl;
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int a = count(s.begin(), s.end(), '0');
    int b = count(s.begin(), s.end(), '1');
    int c = count(s.begin(), s.end(), '2');
    string ans(n, '+');
    for (int i = 0; i < n; ++i) {
      if (i < a + c || i >= n - b - c) ans[i] = '?';
      if (i < a || i >= n - b || k == n) ans[i] = '-';
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
void solve() {                    
    int n;
    string s;
    cin >> n >> s;
    int cur = count(s.begin(), s.end(), 'a') - count(s.begin(), s.end(), 'b');
    map<int, int> lst;
    int pr = 0;
    lst[pr] = -1;
    int ans = n;
    forn(i, n){
        pr += s[i] == 'a' ? 1 : -1;
        lst[pr] = i;
        if (lst.count(pr - cur))
            ans = min(ans, i - lst[pr - cur]);
    }
    cout << (ans == n ? -1 : ans) << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    forn(i, t) solve();
}

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    maxk = n * (n - 1) // 2
    dp = [[False for i in range(maxk + 1)] for j in range(n + 1)]
    p = [[-1 for i in range(maxk + 1)] for j in range(n + 1)]
    dp[0][0] = True
    for j in range(n):
        for x in range(maxk + 1):
            for y in range(1, n - j + 1):
                if not dp[j][x]:
                    continue
                add = y * (y - 1) // 2
                dp[j + y][x + add] = True
                p[j + y][x + add] = y
    k = maxk - k
    if dp[n][k]:
        ans = []
        cur = n
        curk = k
        while cur != 0:
            y = p[cur][curk]
            ans.append(y)
            curk -= y * (y - 1) // 2
            cur -= y
        res = []
        cur = n + 1
        for y in ans:
            for x in range(cur - y, cur):
                res.append(x)
            cur -= y
        print(*res)
    else:
        print(0)

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    fore(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
int ac, dr;
int n;
vector<int> a, d;
 
inline bool read() {
    if(!(cin >> ac >> dr))
        return false;
    cin >> n;
    a.resize(n);
    fore (i, 0, n)
        cin >> a[i];
    d.resize(n);
    fore (i, 0, n)
        cin >> d[i];
    return true;
}
 
vector<int> Tadd, Tmin;
 
void push(int v) {
    Tadd[2 * v + 1] += Tadd[v];
    Tadd[2 * v + 2] += Tadd[v];
    Tadd[v] = 0;
}
 
int getmin(int v) {
    return Tmin[v] + Tadd[v];
}
 
void upd(int v) {
    Tmin[v] = min(getmin(2 * v + 1), getmin(2 * v + 2));
}
 
void init(int v, int l, int r) {
    if (l + 1 == r) {
        Tmin[v] = -l;
        return;
    }
    int mid = (l + r) >> 1;
    init(2 * v + 1, l, mid);
    init(2 * v + 2, mid, r);
    upd(v);
}
 
void init(int n) {
    Tadd.assign(4 * n, 0);
    Tmin.resize(4 * n);
    init(0, 0, n);
}
 
void addVal(int v, int l, int r, int lf, int rg, int val) {
    if (l == lf && r == rg) {
        Tadd[v] += val;
        return;
    }
    int mid = (l + r) >> 1;
    push(v);
    if (lf < mid)
        addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
    if (rg > mid)
        addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
    upd(v);
}
 
int firstNeg(int v, int l, int r) {
    if (l + 1 == r) {
        assert(getmin(v) < 0);
        return l;
    }
    push(v);
    int mid = (l + r) >> 1;
    int ans = -1;
    if (getmin(2 * v + 1) < 0)
        ans = firstNeg(2 * v + 1, l, mid);
    else
        ans = firstNeg(2 * v + 2, mid, r);
    upd(v);
    return ans;
}
 
int calcDemand(int i) {
    return min(n, max(a[i] - ac, 0) + max(d[i] - dr, 0));
}
 
inline void solve() {
    init(n + 2);
    fore (i, 0, n) {
        int p = calcDemand(i);
        addVal(0, 0, n + 2, p + 1, n + 2, 1);
    }
 
    int m; cin >> m;
    fore (j, 0, m) {
        int k, na, nd;
        cin >> k >> na >> nd;
        k--;
        int p = calcDemand(k);
        addVal(0, 0, n + 2, p + 1, n + 2, -1);
        a[k] = na;
        d[k] = nd;
        p = calcDemand(k);
        addVal(0, 0, n + 2, p + 1, n + 2, 1);
 
        int ans = firstNeg(0, 0, n + 2);
        cout << ans - 1 << '\n';
    }
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
const int N = 10;
const int LOG = 50;
const int LCM = 2520;
 
int n;
li m;
int a[N], b[N];
li go[LOG][N][LCM];
 
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];
  for (int x = 0; x < n; ++x) {
    for (int y = 0; y < LCM; ++y) {
      go[0][x][y] = ((y + 1) % a[x]) != b[x];
    }
  }
  for (int i = 1; i < LOG; ++i) {
    for (int x = 0; x < n; ++x) {
      for (int y = 0; y < LCM; ++y) {
        go[i][x][y] = go[i - 1][x][y] + go[i - 1][(x + (1LL << (i - 1))) % n][(y + go[i - 1][x][y]) % LCM];  
      }
    }
  }
  if (go[LOG - 1][0][0] < m) {
    cout << -1 << endl;
    return;
  }
  li s = 0, ans = 0;
  for (int i = LOG - 1; i >= 0; --i) {
    if (s + go[i][ans % n][s % LCM] < m) {
      s += go[i][ans % n][s % LCM];
      ans += 1LL << i;
    }
  }
  cout << ans + 1 << endl;
}
 
int main() {
  int t;
  cin >> t;
  while (t--) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
int n, m, k;
 
const int N = 4043;
const int MOD = 998244353;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   
 
int sub(int x, int y)
{
    return add(x, -y);
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}
 
int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}
 
int fact[N];
int rfact[N];
 
void precalc_factorials()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
    for(int i = 0; i < N; i++)
        rfact[i] = binpow(fact[i], MOD - 2);
}
 
int choose(int x, int y)
{
    if(x < 0 || y < 0 || x < y) return 0;
    return mul(fact[x], mul(rfact[y], rfact[x - y]));
}
 
vector<int> prefix_sum(const vector<int>& a)
{
    int n = a.size();
    vector<int> p(n + 1);
    for(int i = 0; i < n; i++) p[i + 1] = add(a[i], p[i]);
    return p;
}
 
int get(const vector<int>& a, int i)
{
    if(a.size() > i) return a[i];
    else return a.back();
}   
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    precalc_factorials();
 
    vector<vector<int>> A(k, vector<int>(n + m));
    for(int x = 0; x < k; x++)
    {
        vector<int> by_rows(n + 1);
        for(int i = 1; i <= n; i++)
            by_rows[i] = mul(choose(n, i), binpow(x, n - i));
        vector<int> pr = prefix_sum(by_rows);
 
        vector<int> by_cols(m + 1);
        for(int i = 1; i <= m; i++)
            by_cols[i] = mul(choose(m, i), binpow(x, m - i));
        vector<int> pc = prefix_sum(by_cols);
 
        for(int i = 1; i <= max(n, m); i++)
        {
            A[x][n + m - i] = sub(mul(get(pr, i + 1), get(pc, i + 1)), mul(get(pr, i), get(pc, i)));
        }     
    }
 
    for(int i = min(n, m); i < n + m; i++)
    {
        int ans = 0;
        for(int j = 0; j < k; j++)
        {
            int cur = mul(choose(k - 1, j), A[k - 1 - j][i]);
            if(j % 2 == 0)
                ans = add(ans, cur);
            else
                ans = add(ans, -cur);
        }
        cout << ans << " ";
    }
    cout << endl;
}

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if sum(a) % 3 == 0:
        print("1 2")
    else:
        print("0 0")

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> pos0;
    vector<int> used(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        --p[i];
        if(p[i] == -1)
            pos0.push_back(i);
        else
            used[p[i]] = 1;
    }
    if(pos0.size() == 1) 
    {
        int unused = 0;
        for(int i = 0; i < n; i++) if(used[i] == 0) unused = i;
        p[pos0[0]] = unused;
    }
    int l = 0, r = n - 1;
    while(l < n && p[l] == l) l++;
    while(r >= 0 && p[r] == r) r--;
    cout << max(0, r - l + 1) << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      if (a[i] > b[i]) swap(a[i], b[i]);
      if (!i || a[i] >= b[i - 1]) ans = (ans * 2LL) % MOD;
    }
    cout << ans << '\n';
  }
}

for _t in range(int(input())):
    n, y = map(int, input().split())
    a = list(map(int, input().split()))
    A = max(a) + 1
    cntTags = [0] * A
    for v in a:
        cntTags[v] += 1
    pSum = [0] * A
    for i in range(1, A):
        pSum[i] = pSum[i - 1] + cntTags[i]
    
    ans = -(10**18)
    if A == 2:
        print(n)
        continue
    for x in range(2, A):
        res = 0
        for price in range(1, A):
            l = x * (price - 1)
            r = min(A - 1, x * price)
            if l >= A:
                break
            cnt = pSum[r] - pSum[l]
            res += cnt * price
            res -= y * max(0, cnt - cntTags[price])
        ans = max(ans, res)
    print(ans)

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int N = 1000043;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}   
 
int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}
 
vector<int> get(const vector<int>& a)
{
    int cur = -1;
    vector<int> res;
    for(auto x : a)
        if(x > cur)
        {
            res.push_back(x);
            cur = x;
        }
    return res;
}
 
struct SegTree
{
    vector<int> f;
    vector<int> t;
    int n;
 
    int getVal(int v, int pos)
    {
        return mul(t[pos], binpow(2, f[v]));
    }   
 
    void push(int v)
    {
        if(f[v] != 0)
        {
            f[2 * v + 1] += f[v];
            f[2 * v + 2] += f[v];
            f[v] = 0;
        }
    }
 
    void resolve(int v, int pos)
    {
        if(f[v] != 0)
        {
            t[pos] = mul(t[pos], binpow(2, f[v]));
            f[v] = 0;    
        }
    }
 
    int get(int v, int l, int r, int pos)
    {
        if(l == r - 1)
            return getVal(v, pos);
        else
        {
            push(v);
            int m = (l + r) / 2;
            if(pos < m)
                return get(v * 2 + 1, l, m, pos);
            else
                return get(v * 2 + 2, m, r, pos);
        }
    }
 
    int get(int pos)
    {
        return get(0, 0, n, pos);
    }
 
    void inc(int v, int l, int r, int pos, int val)
    {
        if(l == r - 1)
        {
            resolve(v, pos);
            t[pos] = add(t[pos], val);
        }
        else
        {
            push(v);
            int m = (l + r) / 2;
            if(pos < m)
                inc(v * 2 + 1, l, m, pos, val);
            else
                inc(v * 2 + 2, m, r, pos, val);
        }
    }
 
    void inc(int pos, int val)
    {
        return inc(0, 0, n, pos, val);
    }
 
    void mulBy2(int v, int l, int r, int L, int R)
    {
        if(L >= R) return;
        if(l == L && r == R)
            f[v]++;
        else
        {
            push(v);
            int m = (l + r) / 2;
            mulBy2(v * 2 + 1, l, m, L, min(R, m));
            mulBy2(v * 2 + 2, m, r, max(L, m), R);
        }
    }
 
    void mulBy2(int l, int r)
    {
        mulBy2(0, 0, n, l, r);   
    }
 
    SegTree(int n = 0)
    {
        this->n = n;
        f.resize(4 * n);
        t.resize(n);
    }
};
 
vector<int> calc(const vector<int>& a, const vector<int>& b)
{
    int n = a.size();
    int m = b.size();
    SegTree tree(m + 1);
    tree.inc(0, 1);
    vector<int> res(n);
    int maxVal = b.back();
    for(int i = 0; i < n; i++)
    {
        int x = a[i];
        if(x > maxVal) continue;
        else
        {
            if (x == maxVal) res[i] = tree.get(m - 1);
            int lf = lower_bound(b.begin(), b.end(), x) - b.begin();
            tree.mulBy2(lf + 1, m + 1);
            if(b[lf] == x)
            {
                int cur = tree.get(lf);
                tree.inc(lf + 1, cur);
            }
        }
    }
    return res; 
}   
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    auto left_view = get(a);
    reverse(a.begin(), a.end());
    auto right_view = get(a);
    reverse(a.begin(), a.end());
 
    auto dpL = calc(a, left_view);
    reverse(a.begin(), a.end());
    auto dpR = calc(a, right_view);
    reverse(a.begin(), a.end());
    reverse(dpR.begin(), dpR.end());
 
    int maxVal = *max_element(a.begin(), a.end());
    int ans = 0;
    int sumLeft = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] > maxVal) continue;
        else
        {   
            if(a[i] == maxVal) ans = add(ans, mul(add(sumLeft, dpL[i]), dpR[i]));
            sumLeft = mul(sumLeft, 2);
            if(a[i] == maxVal) sumLeft = add(sumLeft, dpL[i]);
        }
    }
    cout << ans << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const string al = "()";
 
struct aho_corasick {
    static const int AL = 2;
 
    struct node {
        int nxt[AL], go[AL];
        int p, pch;
        int suf, ssuf;
        bool term;
        
        node() {
            memset(nxt, -1, sizeof(nxt));
            memset(go, -1, sizeof(go));
            suf = ssuf = -1;
            term = false;
        }
    };
 
    vector<node> nodes;
    vector<vector<int>> g;
    
    aho_corasick() {
        nodes.push_back(node());
    }
 
    void add(const string& s) {
        int v = 0;
        forn(i, s.size()) {
            int c = al.find(s[i]);
            if (nodes[v].nxt[c] == -1) {
                nodes.push_back(node());
                nodes[v].nxt[c] = nodes.size() - 1;
                nodes.back().p = v;
                nodes.back().pch = c;
            }
            v = nodes[v].nxt[c];
        }
        nodes[v].term = true;
    }
    
    int go(int v, int c) {
        if (nodes[v].go[c] != -1)
            return nodes[v].go[c];
        if (nodes[v].nxt[c] != -1)
            return nodes[v].go[c] = nodes[v].nxt[c];
        if (v == 0)
            return nodes[v].go[c] = 0;
        return nodes[v].go[c] = go(suf(v), c);
    }
    
    int suf(int v) {
        if (nodes[v].suf != -1)
            return nodes[v].suf;
        if (v == 0 || nodes[v].p == 0)
            return nodes[v].suf = 0;
        return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
    }
    
    int ssuf(int v) {
        if (nodes[v].ssuf != -1)
            return nodes[v].ssuf;
        if (v == 0 || nodes[v].p == 0)
            return nodes[v].ssuf = 0;
        int s = suf(v);
        if (nodes[s].term)
            return nodes[v].ssuf = s;
        return nodes[v].ssuf = ssuf(s);
    }
    
    void build_tree() {
        g.resize(nodes.size());
        forn(v, nodes.size()) {
            int u = suf(v);
            if (v != u)
                g[u].push_back(v);
        }
    }
};
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    forn(i, n) cin >> s[i];
    forn(i, n) if (s[i] == "()"){
        cout << -1 << '\n';
        return 0;
    }
    aho_corasick ac;
    forn(i, n) ac.add(s[i]);
    vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.nodes.size(), vector<char>(k + 1)));
    vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.nodes.size(), vector<pair<int, int>>(k + 1)));
    dp[0][0][0] = true;
    forn(i, k) forn(v, ac.nodes.size()) forn(bal, i + 1) if (dp[i][v][bal]){
        forn(c, 2){
            int nbal = bal + (c == 0 ? 1 : -1);
            if (nbal < 0) continue;
            int u = ac.go(v, c);
            if (ac.nodes[u].term || ac.ssuf(u) != 0) continue;
            dp[i + 1][u][nbal] = true;
            p[i + 1][u][nbal] = {v, c};
        }
    }
    int sv = -1;
    forn(v, ac.nodes.size()) if (dp[k][v][0]){
        sv = v;
        break;
    }
    if (sv == -1){
        cout << 2 << '\n';
        vector<string> res(2);
        forn(i, k / 2){
            res[0] += "()";
            res[1] += '(';
        }
        forn(i, k / 2){
            res[1] += ')';
        }
        vector<vector<int>> ans(2);
        forn(i, n){
            bool any = false;
            forn(j, int(s[i].size()) - 1)
                any |= s[i][j] == s[i][j + 1];
            ans[!any].push_back(i);
        }
        forn(i, 2){
            cout << res[i] << '\n';
            cout << ans[i].size() << '\n';
            for (int j : ans[i]) cout << j + 1 << " ";
            cout << '\n';
        }
    }
    else{
        cout << 1 << '\n';
        string res = "";
        int bal = 0, v = sv;
        for (int i = k; i > 0; --i){
            auto [u, c] = p[i][v][bal];
            v = u;
            res += al[c];
            bal -= c == 0 ? 1 : -1;
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
        cout << n << '\n';
        forn(i, n) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const string al = "()";
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    forn(i, n) cin >> s[i];
    forn(i, n) if (s[i] == "()"){
        cout << -1 << '\n';
        return 0;
    }
 
    vector<string> ac(1, "");
    forn(i, n) forn(j, s[i].size())
        ac.push_back(s[i].substr(0, j + 1));
    sort(ac.begin(), ac.end());
    ac.resize(unique(ac.begin(), ac.end()) - ac.begin());
 
    vector<char> bad(ac.size());
    set<string> tot(s.begin(), s.end());
    vector<vector<int>> go(ac.size(), vector<int>(2));
    forn(i, ac.size()) forn(j, ac[i].size() + 1){
        bad[i] |= tot.count(ac[i].substr(j));
        forn(t, 2) if (go[i][t] == 0){
            string nw = ac[i].substr(j) + al[t];
            auto it = lower_bound(ac.begin(), ac.end(), nw);
            if (it != ac.end() && *it == nw)
                go[i][t] = it - ac.begin();
        }
    }
 
    vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.size(), vector<char>(k + 1)));
    vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.size(), vector<pair<int, int>>(k + 1)));
    dp[0][0][0] = true;
    forn(i, k) forn(v, ac.size()) forn(bal, i + 1) if (dp[i][v][bal]){
        forn(c, 2){
            int nbal = bal + (c == 0 ? 1 : -1);
            if (nbal < 0) continue;
            int u = go[v][c];
            if (bad[u]) continue;
            dp[i + 1][u][nbal] = true;
            p[i + 1][u][nbal] = {v, c};
        }
    }
    int sv = -1;
    forn(v, ac.size()) if (dp[k][v][0]){
        sv = v;
        break;
    }
    if (sv == -1){
        cout << 2 << '\n';
        vector<string> res(2);
        forn(i, k / 2){
            res[0] += "()";
            res[1] += '(';
        }
        forn(i, k / 2){
            res[1] += ')';
        }
        vector<vector<int>> ans(2);
        forn(i, n){
            bool any = false;
            forn(j, int(s[i].size()) - 1)
                any |= s[i][j] == s[i][j + 1];
            ans[!any].push_back(i);
        }
        forn(i, 2){
            cout << res[i] << '\n';
            cout << ans[i].size() << '\n';
            for (int j : ans[i]) cout << j + 1 << " ";
            cout << '\n';
        }
    }
    else{
        cout << 1 << '\n';
        string res = "";
        int bal = 0, v = sv;
        for (int i = k; i > 0; --i){
            auto [u, c] = p[i][v][bal];
            v = u;
            res += al[c];
            bal -= c == 0 ? 1 : -1;
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
        cout << n << '\n';
        forn(i, n) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int tc;
    cin >> tc;
    while (tc--){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        reverse(s.begin(), s.end());
        cout << s << '\n';
    }
}

from math import gcd
for _ in range(int(input())):
    a, b, k = map(int, input().split())
    g = gcd(a, b)
    print(1 if a // g <= k and b // g <= k else 2)

def good(x):
    return x % 2 > 0 and x % 3 > 0 and x % 5 > 0 and x % 7 > 0
 
def get_naive(x):
    ans = 0
    for i in range(x):
        if good(i):
            ans += 1
    return ans
 
def get(r):
    return (r // 210) * get_naive(210) + get_naive(r % 210)
 
t = int(input())
for i in range(t):
    l, r = map(int, input().split())
    print(get(r+1) - get(l))

for _ in range(int(input())):
    l, r = map(int, input().split())
 
    def f(x):
        res = 0
        ps = [2, 3, 5, 7]
        for mask in range(16):
            m = 1
            sg = 1
            for i in range(4):
                if (mask >> i) & 1:
                    m *= ps[i]
                    sg = -sg
            res += sg * (x // m)
        return res
    
    print(f(r) - f(l - 1))

#include <bits/stdc++.h>
 
using namespace std;
 
using pt = pair<int, int>;
 
const int MOD = 998244353;
 
int add(int x, int y) {
   x += y;
   if (x >= MOD) x -= MOD;
   if (x < 0) x += MOD;
   return x;
}
 
int mul(int x, int y) {
  return x * 1LL * y % MOD;
}
 
int binpow(int x, int y) {
  int z = 1;
  while (y) {
    if (y & 1) z = mul(z, x);
    x = mul(x, x);
    y >>= 1;
  }
  return z;
}
 
int divide(int x, int y) {
  return mul(x, binpow(y, MOD - 2));
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<pt>> a(m + 1);
  for (int i = 0; i < n; ++i) {
    int l, r, p, q;
    cin >> l >> r >> p >> q;
    a[r].emplace_back(l - 1, divide(p, q));
  }
  vector<int> pr(m + 1);
  pr[0] = 1;
  for (int i = 1; i <= m; ++i) {
    int cur = 1;
    for (auto [_, p] : a[i]) cur = mul(cur, add(1, -p));
    pr[i] = mul(pr[i - 1], cur);
  }
  vector<int> dp(m + 1);
  dp[0] = 1;
  for (int i = 1; i <= m; ++i) {
    for (auto [l, p] : a[i]) { 
      int cur = divide(pr[i], pr[l]);
      cur = divide(cur, add(1, -p));
      cur = mul(cur, p);
      dp[i] = add(dp[i], mul(dp[l], cur));
    }
  }
  cout << dp[m] << endl;  
}

#include <bits/stdc++.h>
 
using namespace std;
 
using pt = pair<int, int>;
 
const int MOD = 998244353;
 
int add(int x, int y) {
     x += y;
     if (x >= MOD) x -= MOD;
     if (x < 0) x += MOD;
     return x;
}
 
int mul(int x, int y) {
    return x * 1LL * y % MOD;
}
 
int binpow(int x, int y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
 
int divide(int x, int y) {
    return mul(x, binpow(y, MOD - 2));
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pt>> a(m + 1);
    vector<int> dp(m + 1);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        int l, r, p, q;
        cin >> l >> r >> p >> q;
        int val = divide(p, q);
        a[r].emplace_back(l - 1, val);
        dp[0] = mul(dp[0], add(1, -val));
    }
    for (int i = 1; i <= m; ++i) {
        for (auto [l, p] : a[i]) { 
            int cur = dp[l];
            cur = divide(cur, add(1, -p));
            cur = mul(cur, p);
            dp[i] = add(dp[i], cur);
        }
    }
    cout << dp[m] << endl;  
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MOD = 998'244'353;
 
void solve(){
    int n, x;
    cin >> n >> x;
    // need sum(mx + 1 - ai) <= mx + 1
    // start with 1, 2, 3, ... n
    // min sum + 1 is n + 1
 
    if (n == 1){
        cout << x << '\n';
        return;
    }
 
    int s_cur = n * (n + 1) / 2;
    int need = s_cur - (n + 1);
 
    // leads to n is O(sqrt(s))
    if (n + need > x){
        cout << 0 << '\n';
        return;
    }
 
    // so we can do dp[sum] knapsack
 
    vector<int> dp(x + 1);
    dp[0] = 1;
 
    // for -1 and 0
    for (int j = 0; j < 2; j++){
        for (int i = 0; i < x; i++){
            dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
        }
    }
 
    for (int i = 1; i <= n - 2; i++){
        for (int j = 0; j < x; j++){
            // increase sum by i -> mx increase by 1 + i
            if (j + i + 1 <= x){
                dp[j + i + 1] = (dp[j + i + 1] + dp[j]) % MOD;
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i <= x; i++){
        int cur = n + need + i;
        if (cur > x){
            break;
        }
        ans = (ans + dp[i]) % MOD;
    }
 
    cout << ans << '\n';
}
 
signed main()
{
#ifdef FELIX
    auto _clock_start = chrono::high_resolution_clock::now();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
#ifdef FELIX
    cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
        chrono::high_resolution_clock::now()
            - _clock_start).count() << "ms." << endl;
#endif
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
const int INF = 1e8;
const string al = "docker";
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int tc;
    cin >> tc;
    while (tc--){
        string s;
        cin >> s;
        int n = s.size();
        int mx = n / 6;
        int m;
        cin >> m;
        vector<int> dx(mx + 2);
        forn(i, m){
            int l, r;
            cin >> l >> r;
            r = min(r, mx);
            if (l > r) continue;
            ++dx[l];
            --dx[r + 1];
        }
        forn(i, mx + 1) dx[i + 1] += dx[i];
 
        int cur = 0;
        vector<int> dif(max(0, n - 5));
        forn(i, n - 5){
            forn(j, 6)
                dif[i] += s[i + j] != al[j];
            cur += dif[i] == 0;
        }
 
        int mxcnt = *max_element(dx.begin(), dx.end());
        int k = -1;
        int ans = INF;
        forn(i, mx + 1){
            if (dx[i] != mxcnt) continue;
            if (i <= cur){
                ans = min(ans, cur - i);
                continue;
            }
            k = i;
            break;
        }
 
        if (k == -1){
            cout << ans << '\n';
            continue;
        }
 
        auto calc = [&](int d){
            vector<pair<long long, int>> dp(n + 1, {(long long)1e18, -1});
            dp[0] = {0, 0};
            forn(i, n){
                dp[i + 1] = min(dp[i + 1], dp[i]);
                if (i + 6 <= n)
                    dp[i + 6] = min(dp[i + 6], {dp[i].first + dif[i] + d, dp[i].second - 1});
            }
            return dp[n];
        };
 
        int l = -INF, r = 0, sv = INF;
        while (l <= r){
            int m = (l + r) / 2;
            auto [val, cnt] = calc(m);
            if (-cnt >= k){
                sv = val - k * 1ll * m;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        ans = min(ans, sv);
 
        cout << ans << '\n';
    } 
}

for _ in range(int(input())):
    a, b, c = map(int, input().split())
    if (a + b + c) % 3 != 0:
        print("NO")
        continue
    x = (a + b + c) // 3
    print("YES" if b <= x else "NO")

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int j = 0; j < n; j++) cin >> a[j];
        vector<int> pmax(n + 1);
        vector<long long> psum(n + 1);
        for(int j = 0; j < n; j++)
        {
            pmax[j + 1] = max(pmax[j], a[j]);
            psum[j + 1] = psum[j] + a[j];
        }
        for(int k = 1; k <= n; k++)
            cout << pmax[n - k + 1] + psum[n] - psum[n - k + 1] << " ";
        cout << endl;
    }
}

def beats(n, x, y):
    if x == 0:
        return y == n - 1
    if x == n - 1:
        return y != 0
    return x > y
 
for _ in range(int(input())):
    n = int(input())
    owner = input()
    good = False
    for i in range(n):
        if owner[i] != 'A':
            continue
        good_move = True
        for j in range(n):
            if owner[j] == 'B' and beats(n, j, i):
                good_move = False
        if good_move:
            good = True
    if good:
        print('Alice')
    else:
        print('Bob')

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 6e6;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  vector<int> p, ip(N, 1);
  for (int i = 2; i < N; ++i) {
    if (!ip[i]) continue;
    p.push_back(i);
    for (int j = i; j < N; j += i) {
      ip[j] = 0;
    }
  }
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());
    int ans = 0;
    long long suma = 0, sump = 0;
    for (int i = 0; i < n; ++i) {
      suma += a[i];
      sump += p[i];
      if (suma >= sump) ans = i + 1;
    }
    cout << n - ans << endl;
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    fore(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
int n, k;
string s;
 
inline bool read() {
    if(!(cin >> n >> k))
        return false;
    cin >> s;
    return true;
}
 
inline void solve() {
    vector<int> d(n + 1, 0);
    vector<vector<int>> nxt(n + 2, vector<int>(k, n));
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        int mx = *max_element(nxt[i].begin(), nxt[i].end());
        d[i] = 1 + d[mx];
        nxt[i][s[i] - 'a'] = i;
    }
 
    int q; cin >> q;
    while (q--) {
        string t; cin >> t;
        int pos = -1;
        for (char c : t)
            pos = nxt[pos + 1][c - 'a'];
        cout << d[pos] << "\n";
    }
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
const long long A = (long long)(1e18);
 
string S(long long x)
{
    string s = to_string(x) + to_string(x + 1);
    sort(s.begin(), s.end());
    return s;
}
 
vector<long long> aux2;
vector<pair<string, long long>> aux;
 
long long get_num(string cur)
{
    int first_non_zero = 0;
    while(cur[first_non_zero] == '0') first_non_zero++;
    swap(cur[first_non_zero], cur[0]);
    return stoll(cur);
}
 
void rec(string cur, bool flag)
{
    if(*max_element(cur.begin(), cur.end()) > '0')
    {
        long long x = get_num(cur);
        aux.push_back(make_pair(S(x), x));
    }
    if(cur.size() < 9)
    {
        if(flag)
            rec(cur + "9", true);
        else
            for(char c = '0'; c <= '9'; c++)
                rec(cur + string(1, c), c < cur.back());    
    }
}   
 
void precalc()
{
    for(char c = '0'; c <= '9'; c++)
        rec(string(1, c), false);
    sort(aux.begin(), aux.end());
    for(int i = 0; i < aux.size(); i++)
        if(i == 0 || aux[i].first != aux[i - 1].first)
            aux2.push_back(aux[i].second);
    sort(aux2.begin(), aux2.end());
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    precalc();
    for(int i = 0; i < t; i++)
    {
        long long n;
        cin >> n;
        cout << upper_bound(aux2.begin(), aux2.end(), n) - aux2.begin() << endl;              
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
using pt = pair<int, int>;
 
const int N = 200007;
 
int n, q;
int k[N];
vector<pt> t[4 * N];
int p[N], e[N], rk[N];
int *pos[3 * N];
int val[3 * N];
int csz;
int ans[N];
 
void upd(int v, int l, int r, int L, int R, pt val) {
  if (L >= R) return;
  if (l == L && r == R) {
    t[v].push_back(val);
    return;
  }
  int m = (l + r) / 2;
  upd(v * 2 + 1, l, m, L, min(R, m), val);
  upd(v * 2 + 2, m, r, max(m, L), R, val);
}
 
void rollback(int tsz) {
  while (csz > tsz) {
    --csz;
    (*pos[csz]) = val[csz];
  }
}
 
pt get(int v) {
  if (p[v] == v) return {v, 0};
  auto [u, d] = get(p[v]);
  return {u, d ^ e[v]};
}
 
void assign(int& x, int y) {
  pos[csz] = &x;
  val[csz] = x;
  ++csz;
  x = y;
}
 
pt unite(int x, int y) {
  auto [v, d1] = get(x);
  auto [u, d2] = get(y);
  if (v == u) return {0, d1 ^ d2};
  if (rk[v] > rk[u]) swap(v, u);
  assign(p[v], u);
  assign(e[v], d1 ^ d2 ^ 1);
  assign(rk[u], rk[v] + rk[u]);
  return {1, 0};
}
 
void solve(int v, int l, int r, int cnt) {
  int tsz = csz;
  for (auto [x, y] : t[v]) {
    auto [f, d] = unite(x, y);
    //cerr << l << " " << r << " " << x + 1 << " " << y + 1 << " " << f << " " << d << endl;
    if (!f) cnt ^= d;
  }
  if (l != r - 1) {
    int m = (l + r) / 2;
    solve(v * 2 + 1, l, m, cnt);
    solve(v * 2 + 2, m, r, cnt);
  } else {
    ans[l] = k[l] % 3;
    if (ans[l] == 2) ans[l] = cnt + 1;
  }
  rollback(tsz);
}
 
int main() {
  cin >> n >> q;
  vector<int> g(n), lst(n);
  for (int i = 0; i < n; ++i) {
    cin >> g[i];
    --g[i];
  }
  for (int i = 0; i < q; ++i) {
    int x, y;
    cin >> x >> y >> k[i];
    --x; --y;
    upd(0, 0, q, lst[x], i, {x, g[x]});
    g[x] = y;
    lst[x] = i;
  }
  for (int i = 0; i < n; ++i) {
    upd(0, 0, q, lst[i], q, {i, g[i]});
    p[i] = i;
    rk[i] = 1;
  }
  solve(0, 0, q, n & 1);
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n';
  }
}

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    ans = 0
    if n % 2 == 1:
        n -= k
        ans = 1
    k -= 1
    ans += (n + k - 1) // k
    print(ans)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    long long ans = 0;
    if (k > 1) {
      sort(a.begin(), a.end(), greater<int>());
      ans = accumulate(a.begin(), a.begin() + k + 1, 0LL);
    } else {
      int l = *max_element(a.begin(), a.end() - 1);
      int r = *max_element(a.begin() + 1, a.end());
      ans = max(l + a.back(), r + a[0]);
    }
    cout << ans << '\n';
  }
}

from bisect import bisect_left

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    ans = 0
    for k in range(1, n):
        x = m - bisect_left(a, k)
        y = m - bisect_left(a, n - k)
        ans += x * y - min(x, y)
    print(ans)

#include <bits/stdc++.h>
 
using namespace std;

using li = long long;

const int B = 60;
const li INF = 1e18;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  array<array<li, B>, B> dp;
  for (int i = 0; i < B; ++i) {
    for (int j = 0; j < B; ++j) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0;
  for (int x = 0; x < B; ++x) {
    for (int i = B - 1; i >= 0; --i) {
      for (int j = B - 1; j >= 0; --j) {
        if (dp[i][j] == INF) continue;
        if (i + x < B) dp[i + x][j] = min(dp[i + x][j], dp[i][j] + (1LL << x));
        if (j + x < B) dp[i][j + x] = min(dp[i][j + x], dp[i][j] + (1LL << x));
      }
    }
  }
  int t;
  cin >> t;
  while (t--) {
    li x, y;
    cin >> x >> y;
    li ans = INF;
    for (int i = 0; i < B; ++i) {
      for (int j = 0; j < B; ++j) {
        if ((x >> i) == (y >> j)) ans = min(ans, dp[i][j]);
      }
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int K = 31;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
int sub(int x, int y)
{
    return add(x, -y);
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}
 
int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
 
int dp[K][2][2][2];
 
int choose2(int n)
{
    return mul(n, mul(sub(n, 1), binpow(2, MOD - 2)));
}   
 
void solve()
{
    int n, m, A, B;
    cin >> n >> m >> A >> B;
 
    memset(dp, 0, sizeof dp);
    dp[0][0][0][0] = 1;
    for(int i = 0; i + 1 < K; i++)
        for(int f1 = 0; f1 <= 1; f1++)
            for(int f2 = 0; f2 <= 1; f2++)
                for(int fx = 0; fx <= 1; fx++)
                {
                    int d = dp[i][f1][f2][fx];
                    if(!d) continue;
                    int j = K - 2 - i;
                    int curA = (A >> j) & 1;
                    int curB = (B >> j) & 1;
                    for(int bit_a = 0; bit_a <= 1; bit_a++)
                        for(int bit_b = 0; bit_b <= 1; bit_b++)
                            for(int bit_x = 0; bit_x <= 1; bit_x++)
                            {
                                if(f1 == 0 && bit_a == 1 && curA == 0) continue;
                                if(f2 == 0 && bit_b == 1 && curB == 0) continue;
                                if(fx == 0 && bit_x == 1 && (bit_a == 0 || bit_b == 0)) continue;
                                int nf1 = max(f1, bit_a ^ curA);
                                int nf2 = max(f2, bit_b ^ curB);
                                int nfx = max(fx, bit_x);
                                int& d2 = dp[i + 1][nf1][nf2][nfx];
                                d2 = add(d2, d);
                            }
                }
    int pairs_of_pairs = 0;
    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            pairs_of_pairs = add(pairs_of_pairs, dp[K - 1][i][j][1]);
 
    int comb_a = sub(binpow(2, n), 2);
    int comb_b = sub(binpow(2, m), 2);
 
    int ans = mul(pairs_of_pairs, mul(comb_a, comb_b));
    ans = add(ans, mul(add(A, 1), add(B, 1)));
    ans = add(ans, mul(add(A, 1), mul(comb_b, choose2(add(B, 1)))));
    ans = add(ans, mul(add(B, 1), mul(comb_a, choose2(add(A, 1)))));
    cout << ans << endl;
}
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();    
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
typedef long long li;
typedef pair<int, int> pt;
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
vector<int> Tadd, Tmax;
 
int getmax(int v) {
	return Tmax[v] + Tadd[v];
}
void push(int v) {
	Tadd[2 * v + 1] += Tadd[v];
	Tadd[2 * v + 2] += Tadd[v];
	Tadd[v] = 0;
}
void upd(int v) {
	Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2));
}
void addVal(int v, int l, int r, int lf, int rg, int val) {
	if (l == lf && r == rg) {
		Tadd[v] += val;
		return;
	}
	push(v);
	int mid = (l + r) >> 1;
	if (lf < mid)
		addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
	if (rg > mid)
		addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
	upd(v);
}
 
int n;
vector<int> a;
 
inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	return true;
}
 
inline void solve() {
	vector<int> ask(n, 0);
	int mx = -1;
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] > mx) {
			ask[i] = 1;
			mx = a[i];
		}
	}
	vector<int> left;
	fore (i, 0, n) {
		if (left.empty() || a[left.back()] > a[i])
			left.push_back(i);
	}
 
	vector<pt> seg(n);
	fore (i, 0, n) {
		int lf = upper_bound(left.begin(), left.end(), i, [&left](int v, int i) {
			return a[v] > a[i];
		}) - left.begin();
		int rg = lower_bound(left.begin(), left.end(), i) - left.begin();
		seg[i] = {lf, rg};
	}
 
	Tadd.assign(4 * n, 0);
	Tmax.assign(4 * n, 0);
 
	vector<int> ordToAdd(n);
	iota(ordToAdd.begin(), ordToAdd.end(), 0);
	sort(ordToAdd.begin(), ordToAdd.end(), [](int i, int j) {
		return a[i] < a[j];
	});
 
	auto addToSeg = [&left, &seg](int id, int val) {
		auto [lf, rg] = seg[id];
		if (lf < rg)
			addVal(0, 0, sz(left), lf, rg, val);
	};
 
	int ans = 0;
	int pos = 0;
	vector<int> added(n, 0);
	for (int i = n - 1; i >= 0; i--) {
		while (pos < n && a[ordToAdd[pos]] < a[i]) {
			if (ordToAdd[pos] <= i) {
				addToSeg(ordToAdd[pos], 1);
				added[ordToAdd[pos]] = 1;
			}
			pos++;
		}
		if (ask[i]) {
			auto [lf, rg] = seg[i];
			ans = max(ans, 1 + (lf < rg ? 1 + getmax(0) : 0));
		}
		if (added[i]) {
			addToSeg(i, -1);
			added[i] = 0;
		}
	}
	cout << ans << endl;
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int t; cin >> t;
	while(t--) {
		(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

t = int(input())
for i in range(t):
    n = int(input())
    ans = 3 * (n // 15)
    n %= 15
    for j in range(n + 1):
        if j % 3 == j % 5:
            ans += 1
    print(ans)

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    li n, x, k;
    cin >> n >> x >> k;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
      x += (s[i] == 'L' ? -1 : +1);
      --k;
      if (!x) break;
    }
    li ans = 0;
    if (!x) {
      ans = 1;
      for (int i = 0; i < n; ++i) {
        x += (s[i] == 'L' ? -1 : +1);
        if (!x) {
          ans += k / (i + 1);
          break;
        }
      }
    }
    cout << ans << '\n';
  }
}

for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    a = list(map(int, input().split()))
    l, r = 0, 10**9
    res = -1
    
    def check(d):
        last = 'R'
        cnt = 0
        for i in range(n):
            if a[i] > d:
                if s[i] == 'B' and last != 'B':
                    cnt += 1
                last = s[i]
        return cnt <= k
    
    while l <= r:
        m = (l + r) // 2
        if check(m):
            res = m
            r = m - 1
        else:
            l = m + 1
    print(res)

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  if (x < 0) x += MOD;
  return x;
}
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> p(n), d(n);
    vector<vector<int>> vs(n);
    for (int v = 1; v < n; ++v) {
      cin >> p[v];
      --p[v];
      d[v] = d[p[v]] + 1;
      vs[d[v]].push_back(v);
    }
    vector<int> dp(n), tot(n);
    dp[0] = tot[0] = 1;
    for (int i = 1; i < n; ++i) {
      for (int v : vs[i]) {
        dp[v] = add(tot[d[v] - 1], d[v] == 1 ? 0 : -dp[p[v]]);
        tot[d[v]] = add(tot[d[v]], dp[v]);
      }
    }
    int ans = 0;
    for (int v = 0; v < n; ++v) {
      ans = add(ans, dp[v]);
    }
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 300003;
const int M = 3 * N;
const int S = 4 * N;
 
struct segtree
{
    vector<int> T;
 
    void add(int v, int l, int r, int pos, int val)
    {
        T[v] += val;
        if(l != r - 1)
        {
            int m = (l + r) / 2;
            if(pos < m) add(v * 2 + 1, l, m, pos, val);
            else add(v * 2 + 2, m, r, pos, val);
        }
    }
 
    int get(int v, int l, int r, int L, int R)
    {
        if(L >= R) return 0;
        if(l == L && r == R) return T[v];
        int m = (l + r) / 2;
        return get(v * 2 + 1, l, m, L, min(m, R)) + get(v * 2 + 2, m, r, max(m, L), R);
    }
 
    int getSumLess(int l)
    {
        return get(0, 0, S, 0, l + M);
    }
 
    void add(int pos, int val)
    {
        add(0, 0, S, pos + M, val);
    }
 
    segtree()
    {
        T.resize(4 * S);
    }
};
 
int threshold[] = {0, 1, 1, -2};
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> p(n + 1);
    for(int i = 0; i < n; i++)
        p[i + 1] = p[i] + (s[i] == '1' ? -3 : 1);
    vector<segtree> trees(4);
    long long ans = 0;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            int len = (i - j + 4) % 4;
            int bound = p[i] - threshold[len];
            ans += trees[j].getSumLess(bound); 
        }
        trees[i % 4].add(p[i], 1);
    }
    cout << ans << endl;
}

#include<bits/stdc++.h>
 
using namespace std;             
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<long long> cnt(1 << n);
    for(int i = 0; i < m; i++)
    {
        string s;
        cin >> s;
        int mask = 0;
        for(auto c : s) mask += (1 << (c - 'A'));
        cnt[mask]++;
    }
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
 
    vector<bool> odd(n);
    int odd_pizzas = 0;
    int odd_mask = 0;
    for(int i = 0; i < n; i++)
        if(a[i] % 2 == 1)
        {
            odd[i] = true;
            odd_pizzas++;
            odd_mask += (1 << i);
        }
 
    // calculating the number of bits representing odd-sized pizzas in each mask
    vector<int> cnt_odd(1 << n);
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            if(odd[j] && ((i >> j) & 1) == 1)
                cnt_odd[i]++;
 
    // transforming the sequence a to a' (and b to b', since a and b are the same)
    vector<vector<long long>> A(odd_pizzas + 1, vector<long long>(1 << n, 0ll));
    for(int i = 0; i < (1 << n); i++)
        A[cnt_odd[i]][i] = cnt[i];
 
    // applying SOS DP to every row of the matrix
    for(int k = 0; k <= odd_pizzas; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < (1 << n); j++)
                if((j >> i) & 1)
                    A[k][j] += A[k][j ^ (1 << i)];
 
    // getting the SOS DP of the matrix c' from the editorial
    vector<vector<long long>> B(odd_pizzas + 1, vector<long long>(1 << n, 0ll));
    for(int x = 0; x <= odd_pizzas; x++)
        for(int y = 0; y <= odd_pizzas - x; y++)
            for(int i = 0; i < (1 << n); i++)
                B[x + y][i] += A[x][i] * A[y][i];
 
    // applying inverse SOS DP to every row
    for(int k = 0; k <= odd_pizzas; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < (1 << n); j++)
                if((j >> i) & 1)
                    B[k][j] -= B[k][j ^ (1 << i)];
 
    int size_ans = 0;
    for(auto x : a) size_ans += x;
    vector<long long> ans(size_ans + 1);
    for(int i = 0; i < (1 << n); i++)
    {
        long long cur_cnt = B[cnt_odd[i]][i];
        int sum = 0;
        for(int j = 0; j < n; j++)
            if((i >> j) & 1)
                sum += a[j];
        ans[sum] += cur_cnt;
    }
 
    for(int i = 0; i < (1 << n); i++)
    {
        if(i & odd_mask) continue;
        int sum = 0;
        for(int j = 0; j < n; j++)
            if((i >> j) & 1)
                sum += a[j];
        ans[sum] -= cnt[i];
    }
    
    reverse(ans.begin(), ans.end());
    
    for(auto x : ans) cout << x / 2 << " ";
    cout << endl;
}

t = int(input())
for i in range(t):
    n = int(input())
    ans = 1
    while n > 3:
        n //= 4
        ans *= 2
    print(ans)

import sys
 
sys.set_int_max_str_digits(6000)
 
def fact(x):
    if x == 0:
        return 1
    return x * fact(x - 1)
 
t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    n = min(n, 7)
    s = int(str(k) * fact(n))
    for i in range(1, 10, 2):
        if s % i == 0:
            print(i, end = ' ')
    print()

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l1, r1 = 0, 0
	l2, r2 = 2*10**9, -2*10**9
	
	pr = 0
	mnl, mxl = 0, 0
	mnr, mxr = 2*10**9, -2*10**9
	for i in range(n):
		pr += a[i]
		if a[i] != -1 and a[i] != 1:
			mnr, mxr = mnl, mxl
			mnl, mxl = pr, pr
		l1 = min(l1, pr - mxl)
		r1 = max(r1, pr - mnl)
		l2 = min(l2, pr - mxr)
		r2 = max(r2, pr - mnr)
		mnl = min(mnl, pr)
		mxl = max(mxl, pr)
	res = []
	if l2 > r1:
		res = list(range(l1, r1 + 1)) + list(range(l2, r2 + 1))
	elif r2 < l1:
	    res = list(range(l2, r2 + 1)) + list(range(l1, r1 + 1))
	else:
		res = list(range(min(l1, l2), max(r1, r2) + 1))
	print(len(res))
	print(*res)

#include<bits/stdc++.h>
 
using namespace std;
 
long long gcd(long long x, long long y)
{
    if(x == 0) return y;
    else return gcd(y % x, x);
}
 
void solve()
{
    long long l, r, g;
    scanf("%lld %lld %lld", &l, &r, &g);
    long long L = l + (l % g == 0 ? 0 : g - (l % g));
    long long R = r - r % g;
    for(int i = 0; i <= (R - L) / g; i++)
        for(int j = 0; j <= i; j++)
            if(gcd(L + j * g, R - (i - j) * g) == g)
            {
                printf("%lld %lld\n", L + j * g, R - (i - j) * g);
                return;
            }   
    puts("-1 -1");
}
 
int main()
{                             
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
struct graph
{
    int V;
    vector<vector<int>> g;
    vector<int> color;
 
    bool dfs(int v)
    {
        if(color[v] != 0) return false;
        color[v] = 1;
        bool res = false;
        for(auto y : g[v])
        {
            if(color[y] == 2) continue;
            else if(color[y] == 0)
                res |= dfs(y);
            else res = true;
        }
        color[v] = 2;
        return res;
    }
 
    void add_edge(int x, int y)
    {
        g[x].push_back(y);
    }
 
    graph(int V)
    {
        this->V = V;
        this->g.resize(V);
        this->color.resize(V);
    };
};
 
int get_bit(int x, int y)
{
    return (x >> y) & 1;
}
 
bool check(const vector<vector<int>>& a, const vector<vector<int>>& b, int k)
{
    int n = a.size();
    int m = a[0].size();
    vector<bool> must_row(n);
    vector<bool> must_col(m);
    auto G = graph(n + m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(get_bit(a[i][j], k) != get_bit(b[i][j], k))
            {
                if(get_bit(b[i][j], k) == 0) must_row[i] = true;
                else must_col[j] = true;
            }
            if(get_bit(b[i][j], k) == 0) G.add_edge(j + n, i);
            else G.add_edge(i, j + n);
        }                 
    for(int i = 0; i < n; i++)
        if(must_row[i] && G.dfs(i))
            return false;
    for(int j = 0; j < m; j++)
        if(must_col[j] && G.dfs(j + n))
            return false;
    return true;
}
 
void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    auto b = a;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &b[i][j]);
    for(int i = 0; i < 30; i++)
    {
        if(!check(a, b, i))
        {
            puts("No");
            return;
        }
    }
    puts("Yes");
}
 
int main()
{                             
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
const int MOD = 998244353;
 
int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	return a;
}
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
struct state{
	int mx, cnt;
};
 
void merge(state &a, int mx, int cnt){
	if (a.mx > mx) return;
	if (a.mx < mx) a.mx = mx, a.cnt = 0;
	a.cnt = add(a.cnt, cnt);
}
 
state dp[52][64][2];
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	int mx = *max_element(a.begin(), a.end());
	vector<vector<int>> cnt(n + 1, vector<int>(mx + 1));
	forn(i, n){
		cnt[i + 1] = cnt[i];
		++cnt[i + 1][a[i]];
	}
	forn(_, q){
		int l, r;
		cin >> l >> r;
		--l;
		memset(dp, -1, sizeof(dp));
		dp[0][0][0] = {0, 1};
		forn(i, mx + 1){
			int c = cnt[r][i] - cnt[l][i];
			int c2 = c * 1ll * (c - 1) / 2 % MOD;
			forn(val, 64) forn(fl, 2) if (dp[i][val][fl].cnt >= 0){
				if (c > 0)
					merge(dp[i + 1][val ^ i][true], dp[i][val][fl].mx + c - 1, mul(dp[i][val][fl].cnt, c));
				if (c > 1)
					merge(dp[i + 1][val][true], dp[i][val][fl].mx + c - 2, mul(dp[i][val][fl].cnt, c2));
				merge(dp[i + 1][val][fl], dp[i][val][fl].mx + c, dp[i][val][fl].cnt);
			}
		}
		auto ans = dp[mx + 1][0][1];
		if (ans.cnt == -1)
			cout << -1 << '\n';
		else
			cout << ans.mx << ' ' << ans.cnt << '\n';
	}
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int t; cin >> t;
	while (t--) {
		int X, Y, K;
		cin >> X >> Y >> K;
		int M = min(X, Y);
		cout << "0 0 " << M << " " << M << endl;
		cout << "0 " << M << " " << M << " 0" << endl;
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    
    long long ans = 1e18;
    
    auto upd = [&](vector<long long> a) {
      sort(a.begin(), a.end());
      for (int i = 1; i < (int)a.size(); ++i)
        if (a[i - 1] == a[i]) return;
      long long res = 0;
      for (int i = 0; i < (int)a.size(); i += 2)
        res = max(res, a[i + 1] - a[i]);
      ans = min(ans, res);
    };
    
    if (n % 2 == 0) {
      upd(a);
      cout << ans << '\n';
      continue;
    }
    
    for (int i = 0; i < n; ++i) {
      for (int x : {-1, 1}) {
        a.push_back(a[i] + x);
        upd(a);
        a.pop_back();
      }
    }
    
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 400043;
char buf[N];
 
bool can(const string& s, int k)
{
    int n = s.size();
    vector<int> used(n);
    for(int i = n - 1; i >= 0; i--)
        if(k > 0 && s[i] == '1')
        {
            used[i] = 1;
            k--;
        }
    int cur = 0;
    for(int i = 0; i < n; i++)
        if(used[i])
        {
            cur--;
            if(cur < 0) return false;
        }
        else cur++;
    return true;
}   
 
void solve()
{
    int n;
    scanf("%d", &n);
    scanf("%s", buf);                         
    if(n == 1)
    {
        puts("1");
        return;
    }
    string s = buf;
    int count_1 = 0;
    for(auto x : s) if (x == '1') count_1++;
    int l = 1;
    int r = count_1 + 1;
    while(r - l > 1)
    {
        int mid = (l + r) / 2;
        if(can(s, mid))
            l = mid;
        else
            r = mid;
    }
    long long ans = 0;
    for(int i = n - 1; i >= 0; i--)
        if(s[i] == '1' && l > 0)
            l--;
        else
            ans += (i + 1);
    printf("%lld\n", ans);
}
 
int main()
{
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
        solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int n;
 
vector<long long> a;
vector<long long> pa;
vector<long long> ppa;
vector<long long> start;
vector<long long> block;
vector<long long> pblock;
 
vector<long long> prefix_sums(vector<long long> v)
{
 	int k = v.size();
 	vector<long long> res(k + 1);
 	for(int i = 0; i < k; i++) res[i + 1] = res[i] + v[i];
 	return res;
}
 
long long get_partial(int l, int r1, int r2)
{
	// s(l, r1) + s(l, r1 + 1) + ... + s(l, r2 - 1)
 	if(r2 <= r1) return 0ll;
 	int cnt = r2 - r1;
 	long long rem = pa[l] * cnt;
 	long long add = ppa[r2 + 1] - ppa[r1 + 1];
 	return add - rem;
}
 
pair<int, int> convert(long long i)
{
	int idx = upper_bound(start.begin(), start.end(), i) - start.begin() - 1;
	pair<int, int> res = {idx, i - start[idx] + idx};
	return res; 	
}
 
long long query(long long l, long long r)
{
	pair<int, int> lf = convert(l);
	pair<int, int> rg = convert(r);
	long long res = pblock[rg.first + 1] - pblock[lf.first];
	if(lf.second != lf.first) res -= get_partial(lf.first, lf.first, lf.second);
	if(rg.second != n - 1) res -= get_partial(rg.first, rg.second + 1, n);
	return res;	
}
 
int main()
{
	scanf("%d", &n);
	a.resize(n);
	for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
	pa = prefix_sums(a);
	ppa = prefix_sums(pa);
	start = {0};
	for(int i = n; i >= 1; i--)
		start.push_back(start.back() + i);
	block.resize(n);
	for(int i = 0; i < n; i++)
		block[i] = get_partial(i, i, n);
	pblock = prefix_sums(block);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	long long l, r;
	 	scanf("%lld %lld", &l, &r);
	 	printf("%lld\n", query(l - 1, r - 1));
	}
 
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(a) int((a).size())
 
template<typename T = int>
struct Dinic {
  struct edge {
    int u, rev;
    T cap, flow;
  };
  
  int n, s, t;
  T flow;
  vector<int> lst;
  vector<int> d;
  vector<vector<edge>> g;
  
  Dinic() {}
  
  Dinic(int n, int s, int t) : n(n), s(s), t(t) {
    g.resize(n);
    d.resize(n);
    lst.resize(n);
    flow = 0;
  }
 
  void add_edge(int v, int u, T cap, bool directed = true) {
    g[v].push_back({u, sz(g[u]), cap, 0});
    g[u].push_back({v, sz(g[v]) - 1, directed ? 0 : cap, 0});
  }
 
  T dfs(int v, T flow) {
    if (v == t) return flow;
    if (flow == 0) return 0;
    T result = 0;
    for (; lst[v] < sz(g[v]); ++lst[v]) {
      edge& e = g[v][lst[v]];
      if (d[e.u] != d[v] + 1) continue;
      T add = dfs(e.u, min(flow, e.cap - e.flow));
      if (add > 0) {
        result += add;
        flow -= add;
        e.flow += add;
        g[e.u][e.rev].flow -= add;
      }
      if (flow == 0) break;
    }
    return result;
  }
 
  bool bfs() {
    fill(d.begin(), d.end(), -1);
    queue<int> q({s});
    d[s] = 0;
    while (!q.empty() && d[t] == -1) {
      int v = q.front(); q.pop();
      for (auto& e : g[v]) {
        if (d[e.u] == -1 && e.cap - e.flow > 0) {
          q.push(e.u);
          d[e.u] = d[v] + 1;
        }
      }
    }
    return d[t] != -1;
  }
 
  T calc() {
    T add;
    while (bfs()) {
      fill(lst.begin(), lst.end(), 0);
      while((add = dfs(s, numeric_limits<T>::max())) > 0)
        flow += add;
    }
    return flow;
  }
};
 
const int B = 60;
const int INF = 1e9;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int s = n + B, t = n + B + 1;
    Dinic mf(t + 1, s, t);
    for (int i = 0; i < n; ++i) {
      long long x;
      cin >> x;
      mf.add_edge(s, i, 1);
      for (int j = 0; j < B; ++j) {
        if ((x >> j) & 1) mf.add_edge(i, j + n, INF);
      }
    }
    for (int i = 0; i < B; ++i) mf.add_edge(i + n, t, 1);
    cout << n - mf.calc() << '\n';
  }
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int P = 2000 + 5;
 
struct item{
	int p, t;
};
 
struct minstack {
	stack<item> st;
	stack<array<int, P>> dp;
	int get(int p) {return dp.empty() ? 0 : dp.top()[p];}
	bool empty() {return st.empty();}
	int size() {return st.size();}
	void push(item it) {
		if (empty()){
		    dp.push({});
		    for (int i = 0; i < P; ++i)
		        dp.top()[i] = 0;
		}
		else{
		    dp.push(dp.top());
		}
		st.push(it);
		for (int i = P - it.p - 1; i >= 0; --i)
			dp.top()[i + it.p] = max(dp.top()[i + it.p], dp.top()[i] + it.t);
	}
	void pop() {
		st.pop();
		dp.pop();
	}
	item top() {
		return st.top();
	}
	void swap(minstack &x) {
		st.swap(x.st);
		dp.swap(x.dp);
	}
};
 
struct mindeque {
	minstack l, r, t;
	void rebalance() {
		bool f = false;
		if (r.empty()) {f = true; l.swap(r);}
		int sz = r.size() / 2;
		while (sz--) {t.push(r.top()); r.pop();}
		while (!r.empty()) {l.push(r.top()); r.pop();}
		while (!t.empty()) {r.push(t.top()); t.pop();}
		if (f) l.swap(r);
	}
	int get(int p) {
		int ans = 0;
		for (int i = 0; i <= p; ++i)
			ans = max(ans, l.get(i) + r.get(p - i));
		return ans;
	}
	bool empty() {return l.empty() && r.empty();}
	int size() {return l.size() + r.size();}
	void push_front(item it) {l.push(it);}
	void push_back(item it) {r.push(it);}
	void pop_front() {if (l.empty()) rebalance(); l.pop();}
	void pop_back() {if (r.empty()) rebalance(); r.pop();}
	item front() {if (l.empty()) rebalance(); return l.top();}
	item back() {if (r.empty()) rebalance(); return r.top();}
	void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}
};
 
struct edge{
	int u, tp, p, t;
};
 
struct query{
	int i, p;
};
 
vector<vector<edge>> g;
vector<vector<query>> qs;
vector<int> ans;
mindeque ks;
 
void dfs(int v){
	for (auto& [i, p] : qs[v]){
		ans[i] = ks.get(p);
	}
	for (auto& [u, tp, p, t] : g[v]){
		if (tp == 0){
			dfs(u);
		}
		else if (tp == -1){
		    auto it = ks.front();
		    ks.pop_front();
			dfs(u);
			ks.push_front({it.p, it.t});
		}
		else{
			ks.push_back({p, t});
			dfs(u);
			ks.pop_back();
		}
	}
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int q;
	cin >> q;
	vector<int> st(1);
	vector<int> where(q, -1);
	int cnt = 1, cnt_real = 1;
	where[0] = 0;
	g.push_back({});
	qs.push_back({});
	
	auto copy_shop = [&](int x, bool real){
		g.push_back({});
		qs.push_back({});
		st.push_back(st[x]);
		if (real){
			where[cnt_real] = cnt;
			++cnt_real;
		}
		++cnt;
	};
	
	forn(i, q){
		int tp, x;
		cin >> tp >> x;
		--x;
		int v = where[x], u = -1;
		if (tp != 4){
			copy_shop(v, tp == 1);
			u = cnt - 1;
		}
		if (tp == 1){
			g[v].push_back({u, 0, -1, -1});
			continue;
		}
		if (tp == 3){
			g[v].push_back({u, -1, -1, -1});
			++st[u];
			where[x] = u;
			continue;
		}
		int p;
		cin >> p;
		if (tp == 4){
			qs[v].push_back({i, p});
			continue;
		}
		int t;
		cin >> t;
		g[v].push_back({u, 1, p, t});
		where[x] = u;
	}
	
	ans.assign(q, -1);
	dfs(0);
	forn(i, q) if (ans[i] != -1) cout << ans[i] << '\n';
	return 0;
}