#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
	string s;
	cin >> s;
	int n = s.size();
	int idx = -1;
	for(int i = 0; i + 1 < n; i++)
		if(s[i] == s[i + 1])
			idx = i;
	if(idx == -1)
	{
		if(s.back() == 'a') cout << (s + "b") << endl;
		else cout << (s + "a") << endl;
	}
	else
	{
		string t = "a";
		if(s[idx] == 'a') t = "b";
		cout << s.substr(0, idx + 1) + t + s.substr(idx + 1) << endl;
	}
}
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<string> s(2);
    for (auto& x : s) cin >> x;
    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
      bool ok = true;
      ok &= (s[0][i] == '.' && s[1][i] == '.');
      ok &= (s[0][i - 1] != s[1][i - 1]);
      ok &= (s[0][i + 1] != s[1][i + 1]);
      ok &= (s[0][i - 1] == s[0][i + 1]);
      ans += ok;
    }
    cout << ans << '\n';
  }
}

import java.util.LinkedList
 
fun main() {
    repeat(readln().toInt()) {
        val n = readln().toInt()
        val s = readln()
 
        var ans = 0L
        val bracketPositions = LinkedList<Int>()
        for (i in s.indices) {
            var c = s[i]
            if (c == '_') {
                c = if (bracketPositions.isEmpty()) '(' else ')'
            }
            if (c == ')') {
                ans += i - bracketPositions.pollLast()
            }
            else
                bracketPositions.addLast(i)
        }
        println(ans)
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e9;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        g[p - 1].push_back(i);
    }
    
    auto check = [&](auto&& self, int v, int x) -> bool {
      if (x > INF) return false;
      bool isLeaf = true;
      if (v) x += max(0, x - a[v]);
      for (auto u : g[v]) {
        isLeaf = false;
        if (!self(self, u, x)) return false;
      }
      return (!isLeaf || x <= a[v]);
    };
    
    int l = 1, r = INF;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (check(check, 0, mid)) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    
    cout << a[0] + l - 1 << '\n';
  }
}

#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct query{
	int i, j;
};
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	vector<vector<query>> q(n + 1);
	forn(j, m){
		int i, x;
		cin >> i >> x;
		--i;
		q[x].push_back({i, j});
	}
	forn(i, n + 1){
		sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
			return a.i > b.i;
		});
	}
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int i, int j){
		return a[i] > a[j];
	});
	
	vector<int> cur(n + 1);
	vector<char> ans(m);
	ordered_set<int> alive(ord.begin(), ord.end());
	for (int lvl = 1; lvl <= n; ++lvl){
		for (int k = 1; k <= n; ++k){
			if (cur[k] >= n) break;
			int x = alive.order_of_key(cur[k]);
			int nxt = x + k - 1 >= int(alive.size()) ? n : *alive.find_by_order(x + k - 1);
			while (!q[k].empty() && q[k].back().i <= nxt){
				ans[q[k].back().j] = (a[q[k].back().i] >= lvl);
				q[k].pop_back();
			}
			cur[k] = nxt + 1;
		}
		while (!ord.empty() && a[ord.back()] == lvl){
			alive.erase(ord.back());
			ord.pop_back();
		}
	}
	
	for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
	return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
struct query{
	int i, j;
};
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	vector<vector<query>> q(n + 1);
	forn(j, m){
		int i, x;
		cin >> i >> x;
		--i;
		q[x].push_back({i, j});
	}
	forn(i, n + 1) sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
		return a.i > b.i;
	});
	
	int P = min(1000, n + 1);
	
	vector<char> ans(m);
	for (int k = 1; k < P; ++k){
		int cur = 1;
		int cnt = 0;
		forn(i, n){
			bool fl = false;
			if (a[i] >= cur){
				++cnt;
				fl = true;
				if (cnt == k){
					++cur;
					cnt = 0;
				}
			}
			while (!q[k].empty() && q[k].back().i == i){
				ans[q[k].back().j] = fl;
				q[k].pop_back();
			}
		}
	}
	
	vector<int> sum1(n), sum2(n);
	int p2 = ceil(sqrt(n + 2));
	
	auto add = [&](int i){
		int bl = i / p2;
		for (int j = bl + 1; j * p2 < n; ++j)
			++sum1[j];
		for (int j = i; j < (bl + 1) * p2 && j < n; ++j)
			++sum2[j];
	};
	
	int mx = n / P + 5;
	vector<vector<int>> pos(mx);
	forn(i, n){
		if (a[i] < mx)
			pos[a[i]].push_back(i);
		else
			add(i);
	}
	for (auto &it : pos) reverse(it.begin(), it.end());
	
	for (int k = P; k <= n; ++k){
		while (true){
			int mn = n;
			int who = -1;
			forn(lvl, mx) if (!pos[lvl].empty()){
				int i = pos[lvl].back();
				if (mn < i) continue;
				int cnt = sum1[i / p2] + sum2[i];
				if (a[i] >= cnt / k + 1){
					mn = i;
					who = lvl;
				}
			}
			if (who == -1) break;
			add(mn);
			pos[who].pop_back();
		}
		for (auto it : q[k]){
			int lvl = a[it.i];
			ans[it.j] = (lvl >= mx || pos[lvl].empty() || pos[lvl].back() > it.i);
		}
	}
	
	for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
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 mul(int x, int y)
{
 	return (x * 1ll * y) % MOD;
}
 
int main()
{
 	int n, x, m;
 	cin >> n >> x >> m;
 	vector<int> fib = {0, 1};
 	for(int i = 2; i <= 30; i++)
 		fib.push_back(fib[i - 1] + fib[i - 2]);
 
 
 	int max_sum = fib[x] * n;
 	vector<vector<int>> dp(max_sum + 1, vector<int>(n + 1));
 	dp[0][0] = 1;
 	for(int i = 1; i <= x; i++)
 		for(int j = 0; j < max_sum; j++)
 			for(int k = 0; k < n; k++)
 			{
 			 	if(j + fib[i] <= max_sum)
 			 		dp[j + fib[i]][k + 1] = add(dp[j + fib[i]][k + 1], dp[j][k]);
 			}
	
	vector<int> cost(max_sum + 1, 1e9);
	cost[0] = 0;
	for(int j = 1; j <= max_sum; j++)
		for(int i = 1; i <= 30; i++)
			if(j >= fib[i])
				cost[j] = min(cost[j], cost[j - fib[i]] + 1);
 
	int ans = 0;
	for(int i = 0; i <= max_sum; i++)
		if(cost[i] == m)
			ans = add(ans, dp[i][n]);
	cout << ans << endl;
}

for _ in range(int(input())):
	x, y = map(int, input().split())
	print("YES" if y >= -1 else "NO")

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    int ans = n + m;
    for (int i = 0; i < m; ++i) {
      int j = i;
      for (auto c : a) {
        if (j < m && c == b[j]) ++j;
      }
      ans = min(ans, n + m - (j - i));
    }
    cout << ans << '\n';
  }
}

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

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 x = 0, y = 0, neg = 0, pos = 0;
    for (int i = 0; i < n; ++i) {
      if (a[i] > b[i]) {
        x += a[i];
      } else if (a[i] < b[i]) {
        y += b[i];
      } else {
        neg += (a[i] < 0);
        pos += (a[i] > 0);
      }
    }
    int ans = -1e9;
    for (int i = -neg; i <= pos; ++i)
      ans = max(ans, min(x + i, y + (pos - neg - i)));
    cout << ans << '\n';
  }
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }
    val b = readln().split(" ").map { it.toInt() }
    val c = readln().split(" ").map { it.toInt() }

    val mx = a.maxOrNull()!! + 1

    val best = IntArray(mx) { 1e9.toInt() }
    val calc = IntArray(mx) { 0 }

    for (i in a.indices)
        best[a[i]] = minOf(best[a[i]], a[i] - b[i])
    for (v in 1 until mx)
        best[v] = minOf(best[v], best[v - 1])

    for (v in 1 until mx)
        if (v >= best[v])
            calc[v] = 2 + calc[v - best[v]]

    var ans = 0L
    for (v in c) {
        var cur = v
        if (cur >= mx) {
            val k = (cur - mx + 1 + best[mx - 1]) / best[mx - 1]
            ans += 2L * k
            cur -= k * best[mx - 1]
        }
        ans += calc[cur]
    }
    println(ans)
}

#include<bits/stdc++.h>

using namespace std;

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 mul(int x, int y)
{
 	return (x * 1ll * y) % MOD;
}

int main()
{
	int n;
	cin >> n;
	int k;
	cin >> k;
	vector<vector<int>> dp(n + 1, vector<int>(k + 1));
	dp[0][0] = 1;
	vector<int> sum(k + 1);
	sum[0] = 1;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j <= k; j++)
		{
			int& d = dp[i + 1][min(j + 1, k)];
		 	d = add(d, sum[j]);
		 	if(i >= 2 && i != n - 1)
		 		d = add(d, -dp[i - 1][j]); 
		}
		for(int j = 0; j <= k; j++)
			sum[j] = add(sum[j], dp[i + 1][j]);
	}
	cout << dp[n][k] << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct edge{
	int v, u;
};

vector<vector<int>> g, tg;
vector<int> ord;
vector<char> used;
vector<int> clr;

void ts(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		ts(u);
	ord.push_back(v);
}

void dfs(int v, int k){
	clr[v] = k;
	for (int u : tg[v]) if (clr[u] == -1)
		dfs(u, k);
}

vector<long long> rk, p;
long long sum;
vector<long long*> where;
vector<long long> val;

long long cost(int x){
	return x == 1 ? 0ll : x * 1ll * x;
}

int getp(int a){
	return a == p[a] ? a : getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (clr[a] != clr[b]) return;
	if (rk[a] < rk[b]) swap(a, b);
	where.push_back(&sum);
	val.push_back(sum);
	sum -= cost(rk[a]);
	sum -= cost(rk[b]);
	sum += cost(rk[a] + rk[b]);
	where.push_back(&rk[a]);
	val.push_back(rk[a]);
	rk[a] += rk[b];
	where.push_back(&p[b]);
	val.push_back(p[b]);
	p[b] = a;
}

vector<edge> e;
vector<long long> ans;

void calc(int l, int r, const vector<int> &cur){
	if (l == r - 1){
		ans.push_back(sum);
		return;
	}
	int m = (l + r) / 2;
	for (int i : cur) if (i < m){
		int v = getp(e[i].v), u = getp(e[i].u);
		for (int w : {v, u}) if (used[w]){
			g[w].clear();
			tg[w].clear();
			clr[w] = -1;
			used[w] = false;
		}
		g[v].push_back(u);
		tg[u].push_back(v);
	}
	ord.clear();
	for (int i : cur) if (i < m){
		for (int v : {getp(e[i].v), getp(e[i].u)}) if (!used[v]){
			ts(v);
		}
	}
	reverse(ord.begin(), ord.end());
	int k = 0;
	for (int v : ord) if (clr[v] == -1){
		dfs(v, k);
		++k;
	}
	int tim = val.size();
	for (int i : cur) if (i < m) unite(e[i].v, e[i].u);
	vector<int> tol, tor;
	for (int i : cur){
		if (i >= m)
			tor.push_back(i);
		else if (getp(e[i].v) == getp(e[i].u))
			tol.push_back(i);
		else
			tor.push_back(i);
	}
	calc(m, r, tor);
	while (int(val.size()) > tim){
		*where.back() = val.back();
		where.pop_back();
		val.pop_back();
	}
	calc(l, m, tol);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	e.resize(q);
	forn(i, q){
		int x, y;
		char c;
		cin >> x >> y >> c;
		--x, --y;
		if (c == 'R')
			e[i] = {y + n, x};
		else
			e[i] = {x, y + n};
	}
	rk.resize(n + m, 1);
	p.resize(n + m);
	iota(p.begin(), p.end(), 0);
	used.resize(n + m, 0);
	clr.resize(n + m, -1);
	g.resize(n + m);
	tg.resize(n + m);
	vector<int> cur(q);
	iota(cur.begin(), cur.end(), 0);
	calc(0, q + 1, cur);
	ans.pop_back();
	reverse(ans.begin(), ans.end());
	for (long long x : ans) cout << x << '\n';
	return 0;
}

for _ in range(int(input())):
	n = int(input())
	s = input()
	print("YES" if list(s) == sorted(s) else "NO")

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n + 1);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    li sum = 0, ext = 1e18;
    for (int i = 0; i < n; ++i) {
      sum += abs(a[i] - b[i]);
      ext = min(ext, abs(a[i] - b[n]));
      ext = min(ext, abs(b[i] - b[n]));
      if (min(a[i], b[i]) <= b[n] && b[n] <= max(a[i], b[i]))
        ext = 0;
    }
    cout << sum + ext + 1 << '\n';
  }
}

for _ in range(int(input())):
    n, m = map(int, input().split())
    bounds = [n, m]
    a = []
    a.append(list(map(int, input().split())))
    a.append(list(map(int, input().split())))
    
    bad = -1
    badType = -1
    cur = [0, 0]
    ans = 0
    types = [0 for i in range(n + m + 1)]
    for i in range(n + m):
        curType = 0
        if a[0][i] < a[1][i]:
            curType = 1
        if cur[curType] == bounds[curType]:
            curType = 1 - curType
            if bad == -1:
                bad = i
                badType = 1 - curType
        types[i] = curType
        ans += a[types[i]][i]
        cur[types[i]] += 1
        
    res = []
    for i in range(n + m):
        val = ans - a[types[i]][i]
        if bad != -1 and i < bad and types[i] == badType:
            val = val + a[badType][bad] - a[1 - badType][bad] + a[1 - badType][n + m]
        else:
            val = val + a[types[i]][n + m]
        res.append(val)
    res.append(ans)
    print(*res)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    map<int, int> cnt;
    int b = 0;
    ++cnt[b];
    long long ans = 0;
    for (auto& c : s) {
      b += (c == '(' ? +1 : -1);
      ans += cnt[b];
      ++cnt[b];
      while (cnt.begin()->first * 2 < b)
        cnt.erase(cnt.begin());
    }
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 300043;
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 mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}
 
int nxt[N], prv[N];
bool exists[N];
 
int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) nxt[i] = prv[i] = -1;
	exists[n] = true;
	vector<int> l(q), r(q);
	for(int i = 0; i < q; i++) scanf("%d", &l[i]);
	for(int i = 0; i < q; i++) scanf("%d", &r[i]);
	for(int i = 0; i < q; i++)
	{
		int L = l[i], R = r[i];
		if(exists[L])
		{
			exists[R] = true;
			nxt[R] = nxt[L];
			if(nxt[R] != -1) prv[nxt[R]] = R;
			prv[R] = L;
			nxt[L] = R;
		}
		else
		{
			exists[L] = true;
			prv[L] = prv[R];
			if(prv[L] != -1) nxt[prv[L]] = L;
			nxt[L] = R;
			prv[R] = L;
		}
	}
	vector<int> seq;
	int start = -1;
	for(int i = 1; i <= n; i++)
		if(prv[i] == -1 && exists[i])
			start = i;
	seq.push_back(start);
	while(nxt[start] != -1)
	{
		start = nxt[start];
		seq.push_back(start);
	}
	vector<int> cnt_segments(n + 1);
	cnt_segments[seq[0]]++;
	cnt_segments[seq[q]]++;
	for(int i = 0; i < q; i++)
		cnt_segments[max(seq[i], seq[i + 1])]++;
	int ans = 1;
	int places = 0;
	for(int i = n; i >= 1; i--)
	{
		if(exists[i])
			places += cnt_segments[i];
		else
		{
			ans = mul(ans, places);
			places++;
		}
	}
	printf("%d\n", ans);
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
vector<int> h;
vector<vector<int>> g;
 
void dfs(int v, int p = -1){
	for (int u : g[v]) if (u != p){
		dfs(u, v);
		h[v] = max(h[v], h[u] + 1);
	}
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--){
		int n;
		cin >> n;
		g.assign(n, {});
		forn(i, n - 1){
			int v, u;
			cin >> v >> u;
			--v, --u;
			g[v].push_back(u);
			g[u].push_back(v);
		}
		h.assign(n, 0);
		dfs(0);
		set<pair<int, int>> cur;
		forn(i, n) cur.insert({h[i], i});
		vector<int> ans;
		int tmp = n;
		while (!cur.empty()){
			int v = cur.rbegin()->second;
			while (v != -1){
				--tmp;
				cur.erase({h[v], v});
				int pv = -1;
				for (int u : g[v]) if (h[u] == h[v] - 1){
					pv = u;
					break;
				}
				v = pv;
			}
			ans.push_back(tmp);
		}
		for (int i = 0; i < int(ans.size()); i += 2){
			cout << ans[i] << ' ';
		}
		for (int i = (int(ans.size()) + 1) / 2; i < n - 1; ++i){
			cout << 0 << ' ';
		}
		cout << '\n';
	}
	return 0;
}

for _ in range(int(input())):
    n = int(input())
    p = [int(x) - 1 for x in input().split()]
    ans = 3
    for i in range(n):
        if p[p[i]] == i:
            ans = 2
    print(ans)

fun main() {
    repeat(readln().toInt()) {
        val s = readln().map { it.code - '0'.code }
        val zeroes = s.count { it == 0 }
        val cnt = intArrayOf(0, 0)
        var ans = 0L
        for (c in s) {
            cnt[c]++
            if (c == 0)
                ans += if (cnt[1] > 0) 1 else 0
            else
                ans += (zeroes - cnt[0])
        }
        println(ans)
    }
}

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

using li = long long;
const li INF = 1e18;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<li> a(n);
    for (auto& x : a) cin >> x;
    vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= k; ++j) {
        li mn = INF;
        for (int d = 0; j + d <= k && i + d < n; ++d) {
          mn = min(mn, a[i + d]);
          dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
        }
      }
    }
    cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
  }
}

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

#define sz(a) int((a).size())
using li = long long;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return b[i] > b[j];
    });
    li f = 0, p = 0;
    for (int i : ord) p += max(0, b[i] - a[i]);
    li ans = 0;
    multiset<int> s;
    if (sz(s) == k) ans = max(ans, p - f);
    for (int i : ord) {
      p -= max(0, b[i] - a[i]);
      s.insert(a[i]);
      f += a[i];
      if (sz(s) > k) {
        f -= *s.rbegin();
        s.erase(--s.end());
      }
      if (sz(s) == k) ans = max(ans, p - f);
    }
    cout << ans << '\n';
  }
}

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

#define sz(a) int((a).size())

vector<int> t, p;

void push(int v) {
  if (v * 2 + 2 >= sz(t)) return;
  t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v];
  t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v];
  p[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int x) {
  if (L >= R) return;
  if (l == L && r == R) {
    t[v] += x; p[v] += x;
    return;
  }
  int m = (l + r) / 2;
  push(v);
  upd(v * 2 + 1, l, m, l, min(m, R), x);
  upd(v * 2 + 2, m, r, max(m, L), R, x);
  t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}

int get(int v, int l, int r, int L, int R) {
  if (L >= R) return 1e9;
  if (l == L && r == R) return t[v];
  int m = (l + r) / 2;
  push(v);
  return min(
    get(v * 2 + 1, l, m, l, min(m, R)),
    get(v * 2 + 2, m, r, max(m, L), R)
  );
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& x : a) cin >> x, --x;
  t = p = vector<int>(4 * n);
  vector<vector<int>> pos(n);
  int ans = 0, st = 0;
  for (int i = 0; i < n; ++i) {
    int x = a[i];
    pos[x].push_back(i);
    int k = sz(pos[x]);
    if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1);
    if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2);
    if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1);
    if (get(0, 0, n, st, i + 1) == 0) {
      ans += 1;
      st = i + 1;
    }
  }
  cout << ans << '\n';
}

int main() {
  int t;
  cin >> t;
  while (t--) solve();
}

#include<bits/stdc++.h>

using namespace std;

mt19937_64 rnd(12341234);

int n, k;
vector<int> deck;
vector<int> dp;
vector<vector<bool>> odd;
vector<bool> full_odd;
vector<long long> val;
vector<long long> hs;      

bool bad(const vector<bool>& v)
{
    for(int i = 0; i < k; i++)
        if(!v[i])
            return false;
    return true;
}

vector<bool> inv(const vector<bool>& v)
{
    vector<bool> res(k);
    for(int i = 0; i < k; i++)
        res[i] = !v[i];
    return res;
}

vector<bool> get_suffix(int l)
{
    vector<bool> v(k);                     
    for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]];
    return v;
}

int get_next(long long cur, int x)
{
    for(int i = x; i <= n; i += 2)
        if(hs[i] == cur)
            return i;
    return -1;
}                

int main()
{
    cin >> n >> k;
    deck.resize(n);
    for(int i = 0; i < n; i++) cin >> deck[i];
    for(int i = 0; i < n; i++) --deck[i];
    val.resize(k);
    for(int i = 0; i < k; i++)
        while(val[i] == 0)
            val[i] = rnd();

    int max_score = 0;
    dp.resize(n + 1);
    full_odd.resize(k);
    odd.resize(n + 1, vector<bool>(k));
    hs.resize(n + 1);
    long long cur_hash = 0;
    for(int i = 0; i < n; i++)
    {
        cur_hash ^= val[deck[i]];
        if(full_odd[deck[i]]) max_score++;
        full_odd[deck[i]] = !full_odd[deck[i]];
        odd[i + 1] = full_odd;
        hs[i + 1] = cur_hash;
    }   

    for(int i = k; i <= n; i++)
        dp[i] = 1e9;                          
    long long start = 0ll;
    for(int i = 0; i < k; i++) start ^= val[i];
    int pos = get_next(start, k);
    if(pos == -1)
    {
        cout << max_score << endl;  
    }
    else
    {
        dp[pos] = 0;
        int ans = 1e9;
        for(int p = k; p <= n; p += 2)
        {
            if(dp[p] > 1e8) continue;   
            vector<bool> suff = get_suffix(p);
            vector<int> o, e;
            for(int j = 0; j < k; j++)
                if(suff[j])
                    e.push_back(j);
                else
                    o.push_back(j);
            int es = e.size();
            int os = o.size();
            bool flag = true;
            for(int i = 0; i < os && flag; i++)
                for(int j = 0; j < i && flag; j++)
                {
                    int x = o[i];
                    int y = o[j];
                    int add = 0;         
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);
                    if(pos == -1)                  
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }

            for(int i = 0; i < os && flag; i++)
                for(int j = 0; j < es && flag; j++)
                {
                    int x = o[i];
                    int y = e[j];
                    int add = 1;         
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);    
                    if(pos == -1)
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }

            for(int i = 0; i < es && flag; i++)
                for(int j = 0; j < i && flag; j++)
                {
                    int x = e[i];
                    int y = e[j];
                    int add = 2;                             
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);
                    if(pos == -1)
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }
        }
        cout << max_score - ans << endl;
    }       
}

t = int(input())
for i in range(t):
    n, m, k = map(int, input().split())
    max_color = (n + m - 1) / m
    if max_color + k >= n:
        print('NO')
    else:
        print('YES')

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    lst = -1
    ans = n
    for i in range(n):
        if a[i] != a[0]:
            ans = min(ans, i - lst - 1)
            lst = i
    ans = min(ans, n - lst - 1)
    if ans == n:
        print(-1)
    else:
        print(ans)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    string x, y;
    cin >> x >> y;
    int n = x.size();
    bool f = false;
    for (int i = 0; i < n; ++i) {
      if ((x[i] > y[i]) == f) swap(x[i], y[i]);
      f |= (x[i] != y[i]);
    }
    cout << x << '\n' << y << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
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;
}
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  int s = accumulate(a.begin(), a.end(), 0);
  vector<int> dp(s + 1);
  dp[0] = 1;
  for (int i = 0; i < n; ++i)
    for (int j = s - a[i]; j >= 0; --j) 
      dp[j + a[i]] = add(dp[j + a[i]], dp[j]);
  int ans = 0;
  for (int j = 0; j <= s; ++j) 
    ans = add(ans, mul((j + 1) / 2, dp[j]));
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < a[i]; ++j) 
      ans = add(ans, mul(a[i] - (a[i] + j + 1) / 2, dp[j]));
  cout << ans << '\n';
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
int divup(int a, int b){
    return (a + b - 1) / b;
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    int mx = *max_element(a.begin(), a.end());
    vector<long long> ans(mx + 1);
    forn(i, n){
        int coef = 0;
        if (i == 0 || a[i] > a[i - 1]) ++coef;
        if (i + 1 < n && a[i] < a[i + 1]) --coef;
        int r = a[i];
        ans[r] += coef;
        while (r > 0){
            int val = divup(a[i], r);
            int l = divup(a[i], val);
            ans[l - 1] += coef * val;
            ans[r] -= coef * val;
            r = l - 1;
        }
    }
    forn(i, mx) ans[i + 1] += ans[i];
    forn(i, mx) cout << ans[i] << ' ';
    cout << '\n';
    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 n;
    cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    int mx = *max_element(a.begin(), a.end());
    vector<long long> pr(mx + 1);
    forn(i, n){
        int coef = 0;
        if (i == 0 || a[i] > a[i - 1]) ++coef;
        if (i + 1 < n && a[i] < a[i + 1]) --coef;
        pr[a[i]] += coef;
    }
    forn(i, mx) pr[i + 1] += pr[i];
    for (int k = 1; k <= mx; ++k){
        long long ans = 0;
        for (int l = 1, val = 1; l <= mx; l += k, ++val)
            ans += val * 1ll * (pr[min(mx, l + k - 1)] - pr[l - 1]);
        cout << ans << ' ';
    }
    cout << '\n';
    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;
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 MOD = int(1e9) + 7;
int add(int a, int b) {
    a += b;
    while (a >= MOD)
        a -= MOD;
    while (a < 0)
        a += MOD;
    return a;
}
void upd(int &ans, int val) {
    ans = add(ans, val);
}
int mul(int a, int b) {
    return int(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;
}
 
const int N = 3055;
int f[N], invf[N];
 
void precalcFact() {
    f[0] = invf[0] = 1;
    fore (i, 1, N) {
        f[i] = mul(f[i - 1], i);
        invf[i] = binPow(f[i], MOD - 2);
    }
}
int C(int n, int k) {
    if (k < 0 || k > n)
        return 0;
    return mul(f[n], mul(invf[k], invf[n - k]));
}
 
int n, c, k;
 
inline bool read() {
    if(!(cin >> n >> c >> k))
        return false;
    return true;
}
 
int d[N][N], sum[N][N];
 
// d[z][l] - number of strings of length l, with z zeroes and blocks of 1-s shorter than mx
void precalcShort(int mx) {
    memset(d, 0, sizeof d);
    d[0][0] = 1;
    fore (z, 0, n) {
        fore (l, 0, n) {
            if (d[z][l] == 0)
                continue;
            upd(d[z + 1][l + 1], +d[z][l]);
            upd(d[z + 1][min(n, l + mx) + 1], -d[z][l]);
        }
        fore (l, 0, n + 1)
            upd(d[z + 1][l + 1], d[z + 1][l]);
    }
        
    memset(sum, 0, sizeof sum);
    fore (z, 0, n + 1) fore (l, 0, n + 1)
        sum[z][l + 1] = add(sum[z][l], d[z][l]);
    
}
 
//[lf, rg)
int getSum(int z, int lf, int rg) {
    if (z < 0 || z > n || lf >= rg)
        return 0;
    return add(sum[z][rg], -sum[z][lf]);
}
 
// cnt[g] is a number of x <= n with gcd(x, n) = g
vector<int> precalcCnt(int n) {
    vector<int> cnt(n + 1, 0);
    fore (x, 1, n + 1)
        cnt[gcd(x, n)]++;
    return cnt;
}
 
int calcFixedPoints(int g) {
    if (c >= g)
        return c + k >= n;
    
    int cntOnes = (c + k) / (n / g);
    int cntZeros = g - cntOnes;
    
    int all = 0;
    fore (ones, 0, cntOnes + 1)
        upd(all, C(g, ones));
    
    int bad = 0;
    fore (pref, 0, c) {
        int minZeros = max(0, cntZeros - 1);
        int minMid = g - c;
        int sufLen = g - pref - 1;
        fore (z, minZeros, sufLen + 1)
            upd(bad, getSum(z, minMid, sufLen + 1));
    }
    return add(all, -bad);
}
 
inline void solve() {
    precalcFact();
    precalcShort(c);
    auto cnt = precalcCnt(n);
    
    int ans = 0;
    fore (g, 1, n + 1) {
        if (n % g != 0)
            continue;
        
        int cntFP = calcFixedPoints(g);
//      cerr << "g = " << g << " += " << cnt[g] << " * " << cntFP << endl;
        upd(ans, mul(cnt[g], cntFP));
    }
    
//  cerr << "ans/n = " << ans << " " << n << endl;
    cout << mul(ans, binPow(n, MOD - 2)) << 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);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    if (n % 2 == 1) {
      cout << "NO" << '\n';
      continue;
    }
    cout << "YES" << '\n';
    for (int i = 0; i < n / 2; ++i)
      for (int j = 0; j < 2; ++j)
        cout << "AB"[i & 1];
    cout << '\n';
  }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<int> b({a[n - 1]});
    for (int i = n - 2; i >= 0; --i) {
      if (a[i] > b.back()) {
        b.push_back(a[i] % 10);
        b.push_back(a[i] / 10);
      } else {
        b.push_back(a[i]);
      }
    }
    cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n';
  }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<char> ok1(n / 2), ok2(n / 2);
    for (int i = 0; i < 2; ++i) {
      string s;
      cin >> s;
      for (int j = 0; j < n; ++j) if ((i + j) & 1) {
        ok1[(i + j) / 2] |= (s[j] == '>');
        ok2[(j - i + 1) / 2] |= (s[j] == '>');
      }
    }
    bool ans = true;
    for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i];
    cout << (ans ? "YES" : "NO") << '\n';
  }
}

for _ in range(int(input())):
    s = input()
    n = len(s)
    ans = 0
    for d in range(1, n // 2 + 1):
        cnt = 0
        for i in range(n - d):
            cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?'
            if i - d >= 0:
                cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?'
            if i - d >= -1 and cnt == d:
                ans = 2 * d
    print(ans)

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n), c(n);
    for(int i = 0; i < n; i++)
    {
        a[i] = i + 1;
        c[i] = i / k + 1;
    }
    int q = *max_element(c.begin(), c.end());
    for(int i = 1; i <= q; i++)
    {
        int l = find(c.begin(), c.end(), i) - c.begin();
        int r = c.rend() - find(c.rbegin(), c.rend(), i);
        int m = (l + r) / 2;
        reverse(a.begin() + l, a.begin() + m);
        reverse(a.begin() + m, a.begin() + r);
    }
    for(int i = 0; i < n; i++)
        cout << a[i] << " \n"[i == n - 1];
    cout << q << "\n";
    for(int i = 0; i < n; i++)
        cout << c[i] << " \n"[i == n - 1];
}
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

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

const int MOD = 998244353;

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;
}

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 main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  vector<int> suma(n + 1), sumb(n + 1);
  for (int i = 0; i < n; ++i) {
    suma[i + 1] = suma[i] + a[i];
    sumb[i + 1] = sumb[i] + b[i];
  }
  int m = sumb[n];
  vector<int> f(m + 1), invf(m + 1);
  f[0] = 1;
  for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i);
  invf[m] = binpow(f[m], MOD - 2);
  for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i);
  vector<int> sumc(m + 2);
  for (int i = 0; i <= m; ++i)
    sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i])));
  int pw2 = binpow(binpow(2, MOD - 2), m);
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    int k = 2 * (suma[r] - suma[l]) - suma[n];
    int cur = sumb[r] - sumb[l];
    int mx = max(0, min(k + cur, m + 1));
    int cnt = sumc[mx];
    cout << mul(cnt, pw2) << ' ';
  }
}

#include<bits/stdc++.h>

using namespace std;

int n, c;
int g[21][21];

const int INF = int(1e9);

int primMST(int vertex_cover_mask)
{
    vector<int> d(n, INF);
    vector<bool> used(n, false);
    d[0] = 0;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int idx = -1;
        for(int j = 0; j < n; j++)
        {
            if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx]))
                idx = j;
        }
        if(idx == -1) return INF;
        used[idx] = true;
        ans += d[idx];
        for(int k = 0; k < n; k++)
        {
            if(used[k]) 
                continue;
            if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0)
                continue;
            d[k] = min(d[k], g[idx][k]);
        }
    }
    return ans;
}

int main()
{
    cin >> n >> c;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> g[i][j];
            if(g[i][j] == 0) g[i][j] = INF;
        }
    }
    int ans = INF;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        int cur = primMST(mask);
        if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask));
    }
    cout << ans << endl;
}

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    l, r = a.index(1), n - a[::-1].index(1) - 1
    c = a.count(1)
    print(r - l - c + 1)

#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), x(n);
    for (auto& it : a) cin >> it;
    for (auto& it : x) cin >> it;
    vector<long long> s(n + 1);
    for (int i = 0; i < n; ++i) s[abs(x[i])] += a[i];
    bool ok = true;
    long long lft = 0;
    for (int i = 1; i <= n; ++i) {
      lft += k - s[i];
      ok &= (lft >= 0);
    }
    cout << (ok ? "YES" : "NO") << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 300043;
 
int t;
int n, m;
int a[N];
long long sum[N];
int cnt1[N];
 
int main() {
    ios_base::sync_with_stdio(false);
    
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> n >> m;
        memset(sum, 0, sizeof(sum[0]) * (n + 5));
        memset(cnt1, 0, sizeof(cnt1[0]) * (n + 5));
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sum[i + 1] = sum[i] + a[i];
            cnt1[i + 1] = cnt1[i] + (a[i] == 1);
        }
        
        for (int i = 0; i < m; ++i) {
            int l, r;
            cin >> l >> r;
            --l;
            int cur_cnt1 = cnt1[r] - cnt1[l];
            long long cur_sum = sum[r] - sum[l];
            
            if((r - l) + cur_cnt1 <= cur_sum && r - l > 1)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<int> ans(n, n);
    for (int z = 0; z < 2; ++z) {
      vector<long long> s(n + 1);
      for (int i = 0; i < n; ++i) s[i + 1] = s[i] + a[i];
      vector<int> p(n, -1);
      for (int i = 1; i < n; ++i) {
        int j = (z ? n - i - 1 : i);
        int l = 1, r = i;
        while (l <= r) {
          int m = (l + r) / 2;
          if (s[i] - s[i - m] > a[i] && p[i - 1] >= i - m) {
            ans[j] = min(ans[j], m);
            r = m - 1;
          } else {
            l = m + 1;
          }
        }
        if (a[i - 1] > a[i]) ans[j] = 1;
        p[i] = (a[i] == a[i - 1] ? p[i - 1] : i - 1);
      }
      reverse(a.begin(), a.end());
    }
    for (int i = 0; i < n; ++i)
      cout << (ans[i] == n ? -1 : ans[i]) << ' ';
    cout << '\n';
  }
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
int n;
vector<int> a;
vector<vector<int>> g;
 
long long ans;
vector<map<int, int>> cnt;
 
void dfs(int v, int p = -1){
    int bst = -1;
    for (int u : g[v]) if (u != p){
        dfs(u, v);
        if (bst == -1 || cnt[bst].size() < cnt[u].size())
            bst = u;
    }
    for (int u : g[v]) if (u != p && u != bst){
        for (auto it : cnt[u]){
            int x = it.first, y = it.second;
            if (x != a[v]) ans += cnt[bst][x] * 1ll * y;
            cnt[bst][x] += y;
        }
    }
    if (bst != -1) swap(cnt[bst], cnt[v]);
    ans += cnt[v][a[v]];
    cnt[v][a[v]] = 1;
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        a.resize(n);
        forn(i, n) cin >> a[i];
        g.assign(n, {});
        forn(_, n - 1){
            int v, u;
            cin >> v >> u;
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        ans = 0;
        cnt.assign(n, {});
        dfs(0);
        cout << ans << '\n';
    }
    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 all(a) (a).begin(), (a).end()
 
typedef long long li;
typedef pair<int, int> pt;
 
const int INF = int(1e9);
const int MOD = int(1e9) + 7;
 
int add(int a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
    return a;
}
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}
 
namespace SuffixArray {
    string s;
    vector< array<int, 2> > classes;
    
    vector<int> build(const string &bs) {
        s = bs;
        s += '$';
        
        vector<int> c(all(s)), ord(sz(s));
        iota(all(ord), 0);
        classes.resize(sz(s));
 
        for (int len = 1; len < 2 * sz(s); len <<= 1) {
            int half = len >> 1;
            fore (i, 0, sz(s))
                classes[i] = {c[i], c[(i + half) % sz(s)]};
            
            sort(all(ord), [&](int i, int j) {
                return classes[i] < classes[j];
            });
            c[ord[0]] = 0;
            fore (i, 1, sz(ord))
                c[ord[i]] = c[ord[i - 1]] + (classes[ord[i - 1]] != classes[ord[i]]);
        }
        
        c.pop_back();
        for (int &cc : c)
            cc--;
        return c;
    }
};
 
int n, k;
string s;
 
inline bool read() {
    if(!(cin >> n >> k))
        return false;
    cin >> s;
    return true;
}
 
string calcZero(string s) {
    int rem = k;
    int pos = 0;
    for (int i = sz(s) - 1; rem > 0 && i >= 0; i--) {
        if (s[i] == '1')
            continue;
        
        while (pos < sz(s) && s[pos] == '0')
            pos++;
        if (pos >= i)
            break;
        
        swap(s[pos], s[i]);
        rem--;
    }
    return s.substr(s.find('1'));
}
 
string calcOne(string s) {
    reverse(all(s));
    
    auto c = SuffixArray::build(s);
    int cntOnes = count(all(s), '1');
    
    array<int, 3> mn = { 2 * sz(s), INF, -1 };
        
    int u = 0, curOnes = 0;
    fore (i, 0, n) {
        while (u < sz(s) && (u - i < cntOnes || cntOnes - curOnes > k - 1)) {
            curOnes += s[u] == '1';
            u++;
        }
        if (u - i < cntOnes || cntOnes - curOnes > k - 1)
            break;
        
        array<int, 3> curAns = { u - i, c[i], i };
        mn = min(mn, curAns);
        
        curOnes -= s[i] == '1';
    }
    assert(mn[2] >= 0);
    
    string res = s.substr(mn[2], mn[0]);
    int toAdd = cntOnes - count(all(res), '1');
    for (int i = sz(res) - 1; toAdd > 0 && i >= 0; i--) {
        if (res[i] == '0') {
            res[i] = '1';
            toAdd--;
        }
    }
    return res;
}
 
inline void solve() {
    auto s1 = calcZero(s);
    auto s2 = calcOne(s);
 
    if (sz(s1) > sz(s2) || (sz(s1) == sz(s2) && s1 > s2))
        swap(s1, s2);
    
    int res = 0;
    for (char c : s1)
        res = add(mul(res, 2), c - '0');
    cout << res << 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);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = input()
	print("YES" if any([a[i] != c[i] and b[i] != c[i] for i in range(n)]) else "NO")

#include <bits/stdc++.h>
 
using namespace std;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        map<int, int> numOfLens;
        for (int i = 0; i < n; ++i){
            int x;
            cin >> x;
            ++numOfLens[x];
        }
        
        long long res = 0;
        int sum = 0;
        for (auto it : numOfLens) {
            long long cnt = it.second;
            if(cnt >= 3)
                res += cnt * (cnt - 1) * (cnt - 2) / 6;
            if(cnt >= 2)
                res += cnt * (cnt - 1) / 2 * sum;
            sum += cnt;
        }
        
        cout << res << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000;
const int INF = 1'000'000'009;
int t;
 
char type(const vector <int>& a, int id) {
    int distL = (id == 0? INF : a[id] - a[id - 1]);
    int distR = (id + 1 == a.size()? INF : a[id + 1] - a[id]);
    if(distL < distR) return 'L';
    if(distL > distR) return 'R';
    assert(false);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> a(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
            
        vector <int> l(n), r(n);
        for (int i = 1; i < n; ++i)
            r[i] = r[i - 1] + (type(a, i - 1) == 'R'? 1 : a[i] - a[i - 1]);
        for (int i = n - 2; i >= 0; --i)
            l[i] = l[i + 1] + (type(a, i + 1) == 'L'? 1 : a[i + 1] - a[i]);
        
        int m;
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int x, y;
            cin >> x >> y;
            --x, --y;
            if (x < y) 
                cout << r[y] - r[x] << endl;
            else
                cout << l[y] - l[x] << endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n + 2), d(n + 2, INT_MAX);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> d[i];
    set<int> lft, cur;
    for (int i = 0; i < n + 2; ++i) {
      lft.insert(i);
      cur.insert(i);
    }
    for (int z = 0; z < n; ++z) {
      set<int> del, ncur;
      for (int i : cur) {
        auto it = lft.find(i);
        if (it == lft.end()) continue;
        int prv = *prev(it);
        int nxt = *next(it);
        if (a[prv] + a[nxt] > d[i]) {
          del.insert(i);
          ncur.insert(prv);
          ncur.insert(nxt);
        }
      }
      cout << del.size() << ' ';
      for (auto it : del) lft.erase(it);
      cur = ncur;
    }
    cout << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> f(long long x) {
  vector<int> res;
  if (x == 2) {
  	res.push_back(0);
  } else if (x & 1) {
    res = f(x - 1);
    res.push_back(*min_element(res.begin(), res.end()) - 1);
  } else {
    res = f(x / 2);
    res.push_back(*max_element(res.begin(), res.end()) + 1);
  }
  return res;
}
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long x;
    cin >> x;
    auto ans = f(x);
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    cout << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 111;
 
int n, k;
int a[N];
int nxtx[N][N], prvx[N][N];
int nxtnx[N][N], prvnx[N][N];
int dp1[N][N][N], dp2[N][N][N];
 
int calc2(int, int, int);
 
int calc1(int l, int r, int x) {
  l = nxtnx[l][x], r = prvnx[r][x];
  if (l > r) return 0;
  if (dp1[l][r][x] != -1) return dp1[l][r][x];
  dp1[l][r][x] = calc2(l, r, x) + 1;
  for (int i = l; i < r; ++i) dp1[l][r][x] = min(dp1[l][r][x], calc1(l, i, x) + calc1(i + 1, r, x));
  return dp1[l][r][x];
}
 
int calc2(int l, int r, int x) {
  l = nxtx[l][x], r = prvx[r][x];
  if (l > r) return 0;
  if (dp2[l][r][x] != -1) return dp2[l][r][x];
  dp2[l][r][x] = n;
  for (int i = l; i < r; ++i) dp2[l][r][x] = min(dp2[l][r][x], calc2(l, i, x) + calc2(i + 1, r, x));
  for (int y = 0; y < k; ++y) if (x != y) dp2[l][r][x] = min(dp2[l][r][x], calc1(l, r, y)); 
  return dp2[l][r][x];
}
 
void solve() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> a[i], --a[i];
  for (int x = 0; x < k; ++x) prvx[0][x] = prvnx[0][x] = -1;
  for (int i = 0; i < n; ++i) {
    prvx[i][a[i]] = i;
    for (int x = 0; x < k; ++x) prvx[i + 1][x] = prvx[i][x];
    for (int x = 0; x < k; ++x) if (x != a[i]) prvnx[i][x] = i;
    for (int x = 0; x < k; ++x) prvnx[i + 1][x] = prvnx[i][x];
  }
  for (int x = 0; x < k; ++x) nxtx[n][x] = nxtnx[n][x] = n;
  for (int i = n - 1; i >= 0; --i) {
    for (int x = 0; x < k; ++x) nxtx[i][x] = nxtx[i + 1][x];
    nxtx[i][a[i]] = i;
    for (int x = 0; x < k; ++x) nxtnx[i][x] = nxtnx[i + 1][x];
    for (int x = 0; x < k; ++x) if (x != a[i]) nxtnx[i][x] = i;
  }
  memset(dp1, -1, sizeof(dp1));
  memset(dp2, -1, sizeof(dp2));
  int ans = n;
  for (int x = 0; x < k; ++x) ans = min(ans, calc1(0, n - 1, x));
  cout << ans << '\n';
}
 
int main() {
  int t;
  cin >> t;
  while (t--) solve();
}

for _ in range(int(input())):
    n = int(input())
    s = input()
    print(sum([s.count(chr(ord('A') + i)) >= i + 1 for i in range(26)]))

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for(int i = 0; i < n; i++) a[i] = n - i;
	reverse(a.end() - k - 1, a.end());
	for(int i = 0; i < n; i++)
	{
		if(i) cout << " ";
		cout << a[i];
	}
	cout << endl;
}
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
	return 0;
}

fun main() = repeat(readLine()!!.toInt()) {
  val (n, k) = readLine()!!.split(" ").map { it.toInt() }
  val a = readLine()!!.split(" ").map { it.toInt() }
  val b = readLine()!!.split(" ").map { it.toInt() }
  var (res, sum, mx) = intArrayOf(0, 0, 0)
  for (i in 0 until minOf(n, k)) {
    sum += a[i]
    mx = maxOf(mx, b[i])
    res = maxOf(res, sum + mx * (k - i - 1))
  }
  println(res)
}

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	
	def get_best3(a):
		mx1, mx2, mx3 = -1, -1, -1
		for i in range(len(a)):
			if mx1 == -1 or a[i] > a[mx1]:
				mx3 = mx2
				mx2 = mx1
				mx1 = i
			elif mx2 == -1 or a[i] > a[mx2]:
				mx3 = mx2
				mx2 = i
			elif mx3 == -1 or a[i] > a[mx3]:
				mx3 = i
		return (mx1, mx2, mx3)
	
	ans = 0
	for x in get_best3(a):
		for y in get_best3(b):
			for z in get_best3(c):
				if x != y and x != z and y != z:
					ans = max(ans, a[x] + b[y] + c[z])
	print(ans)

#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;
 
// S = sum a_i - sum b_i
// if Bob made all steps: then S = 0 - sum (b_i - 1)
// each Alice step: S += (a_i - 1) + (b_i - 1) i. e. the bigger (a_i + b_i) the better
 
int n;
vector<int> a, b;
 
inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	b.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	fore (i, 0, n)
		cin >> b[i];
	return true;
}
 
inline void solve() {
	vector<int> ids(n);
	iota(ids.begin(), ids.end(), 0);
	
	sort(ids.begin(), ids.end(), [&](int i, int j) {
		return a[i] + b[i] > a[j] + b[j];
	});
	
	li S = 0;
	fore (i, 0, n) {
		if (i & 1)
			S -= b[ids[i]] - 1;
		else
			S += a[ids[i]] - 1;
	}
	cout << S << 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;
	for(int i = 0; i < t; i++)
	{
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	}
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 222222;
 
int n;
int sz[N];
vector<int> g[N];
 
void init(int v) {
  sz[v] = 1;
  for (int u : g[v]) {
    init(u);
    sz[v] += sz[u];
  }
}
 
int calc(int v, int k) {
  int tot = 0, mx = -1;
  for (int u : g[v]) {
    tot += sz[u];
    if (mx == -1 || sz[mx] < sz[u]) mx = u;
  }
  if (tot == 0) return 0;
  if (sz[mx] - k <= tot - sz[mx])
    return (tot - k) / 2;
  int add = tot - sz[mx];
  return add + calc(mx, max(0, k + add - 1));
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; ++i) g[i].clear();
    for (int i = 1; i < n; ++i) {
      int p; cin >> p;
      g[p - 1].push_back(i);
    }
    init(0);
    cout << calc(0, 0) << '\n';
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int add(int x, int y)
{
	return (((x + y) % MOD) + MOD) % MOD;
}
 
int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}
 
mt19937_64 rnd(98275314);
 
long long gen()
{
	long long x = 0;
	while(x == 0)
		x = rnd();
	return x;
}
 
vector<int> c;
vector<int> g;
 
int process_block(int l, int r)
{
	int ans = 0;
	while(l < r)
	{
		if(g[l] != -1 && g[l] < r)
			l = g[l];
		else
		{
			ans++;
			l++;
		}
	}
	return ans;
}
 
void solve()
{
	int n;
	scanf("%d", &n);
	int size = 0, cnt = 1;
	c.resize(n * 2);
	g.resize(n * 2, -1);
	for(int i = 0; i < 2 * n; i++)
	{
		scanf("%d", &c[i]);
		--c[i];
	}
	
	vector<long long> val(n);
	for(int i = 0; i < n; i++) val[i] = gen();
	
	map<long long, int> last;
	long long cur = 0;
	last[0] = 0;
	for(int i = 0; i < n * 2; i++)
	{
		cur ^= val[c[i]];
		if(cur == 0)
		{
			size++;
			cnt = mul(cnt, process_block(last[0], i + 1));
			last.clear();
		}
		else if(last.count(cur))
		{
			g[last[cur]] = i + 1;
		}
		last[cur] = i + 1;
	}
	
	printf("%d %d\n", size, cnt);
	c.clear();
	g.clear();
}
 
int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++) solve();
}

for _ in range(int(input())):
	n = int(input())
	s = input()
	print("NO" if s.count('1') == n else "YES")

fun main(args: Array<String>) {
    repeat(readln().toInt()) {
        val (n, p, l, t) = readln().split(' ').map { it.toLong() }
        val cntTasks = (n + 6) / 7
        
        fun calc(k: Long) = k * l + minOf(2 * k, cntTasks) * t
        var lf = 0L
        var rg = n
        while (rg - lf > 1) {
            val mid = (lf + rg) / 2
            if (calc(mid) >= p)
                rg = mid
            else
                lf = mid
        }
        println(n - rg)
    }
}

from math import gcd
 
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	for i in range(n - 1):
		g = gcd(g, a[i + 1] - a[i])
	g = max(g, 1)
	a.sort()
	j = n - 1
	res = a[-1]
	while True:
		while j >= 0 and a[j] > res:
			j -= 1
		if j < 0 or a[j] != res:
			break
		res -= g
	print((a[-1] * (n + 1) - (sum(a) + res)) // g)

#include <bits/stdc++.h>
 
using namespace std;
 
#define x first
#define y second
 
using pt = pair<int, int>;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<pt> pos(n + 1);
  for (int i = 0; i < n; ++i) {
    pos[i + 1].x = pos[i].x + (s[i] == 'R') - (s[i] == 'L');
    pos[i + 1].y = pos[i].y + (s[i] == 'U') - (s[i] == 'D');
  }
  map<pt, vector<int>> mp;
  for (int i = 0; i <= n; ++i) mp[pos[i]].push_back(i);
  auto check = [&](pt p, int l, int r) {
  	if (!mp.count(p)) return false;
  	auto it = lower_bound(mp[p].begin(), mp[p].end(), l);
  	return it != mp[p].end() && *it <= r;
  };
  while (q--) {
  	int x, y, l, r;
  	cin >> x >> y >> l >> r;
  	int nx = pos[r].x + pos[l - 1].x - x, ny = pos[r].y + pos[l - 1].y - y;
  	bool f = check({x, y}, 0, l - 1)
  	       | check({nx, ny}, l, r - 1)
  	       | check({x, y}, r, n);
  	cout << (f ? "YES" : "NO") << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = int(1e6) + 99;
 
int nxt;
int to[N][26];
int sum[N];
long long res;
 
void add(const string& s) {
    int v = 0;
    ++sum[v];
    for (auto c : s) {
        int i = c - 'a';
        if (to[v][i] == -1)
            to[v][i] = nxt++;
        v = to[v][i];
        ++sum[v];
    }
}
 
void upd(const string& s) {
    int curLen = s.size();
    int v = 0;
    
    for (auto c : s) {
        int i = c - 'a';
        if (to[v][i] == -1) {
            res += sum[v] * 1LL * curLen;
            break;
        } else {
            int nxtV = to[v][i];
            res += (sum[v] - sum[nxtV]) * 1LL * curLen;
            --curLen;
            v = nxtV;
        }
    }
}
 
void solve(int n, vector <string> v) {
    int sumSizes = 0;
    for (int i = 0; i < n; ++i)
        sumSizes += v[i].size();
        
    nxt = 1;
    memset(sum, 0, sizeof sum);
    memset(to, -1, sizeof to);
    
    for(int i = 0; i < n; ++i) 
        add(v[i]);
    for (int i = 0; i < n; ++i) {
        reverse(v[i].begin(), v[i].end());
        upd(v[i]);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector <string> v(n);
    for (int i = 0; i < n; ++i) 
        cin >> v[i];
    
    res = 0;
    solve(n, v);
    for(int i = 0; i < n; ++i)
        reverse(v[i].end(), v[i].end());
    solve(n, v);
    
    cout << res << endl;
    
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 200043;
const int K = 20;
 
typedef array<int, K> base;
int a[N];
vector<int> g[N];
vector<int> path_up[N];
int tin[N], tout[N];
int T = 0;
int fup[N][K];
 
base make_empty()
{
    base b;
    for(int i = 0; i < K; i++)
        b[i] = 0;
    return b;
}
 
int reduce(const base& b, int x)
{
    for(int i = K - 1; i >= 0; i--)
        if(x & (1 << i))
            x ^= b[i];
    return x;
}   
 
bool add(base& b, int x)
{
    x = reduce(b, x);
    if(x != 0)
    {
        for(int i = K - 1; i >= 0; i--)
            if(x & (1 << i))
            {
                b[i] = x;
                return true;
            }
    }   
    return false;
}
 
bool check(const base& b, int x)
{
    return reduce(b, x) == 0;
}
 
vector<int> rebuild_path(const vector<int>& path, int v)
{
    base b = make_empty();
    vector<int> ans;
    if(add(b, a[v])) ans.push_back(v);
    for(auto x : path) if(add(b, a[x])) ans.push_back(x);
    return ans;
}
 
void dfs(int v, int u)
{
    tin[v] = T++;      
    if(u == v)
        path_up[v] = rebuild_path(vector<int>(0), v);
    else
        path_up[v] = rebuild_path(path_up[u], v);
    fup[v][0] = u;
    for(int i = 1; i < K; i++)
        fup[v][i] = fup[fup[v][i - 1]][i - 1];
    for(auto y : g[v])
        if(y != u)
            dfs(y, v);
    tout[v] = T++;   
}
 
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int LCA(int x, int y)
{
    if(is_ancestor(x, y)) return x;
    for(int i = K - 1; i >= 0; i--)
        if(!is_ancestor(fup[x][i], y))
            x = fup[x][i];
    return fup[x][0];
}
 
bool query(int x, int y, int k)
{
    base b = make_empty();
    int z = LCA(x, y);
    for(auto v : path_up[x])
        if(!is_ancestor(v, y))
            add(b, a[v]);
    for(auto v : path_up[y])
        if(!is_ancestor(v, x))
            add(b, a[v]);
    add(b, a[z]);
    return check(b, k);            
}
 
int main()
{
    int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0, 0);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		int x, y, k;
		scanf("%d %d %d", &x, &y, &k);
		--x;
		--y;
		if(query(x, y, k)) puts("YES");
		else puts("NO");
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, x;
    cin >> n >> x;
    int prev = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
      int a; cin >> a;
      ans = max(ans, a - prev);
      prev = a;
    }
    ans = max(ans, 2 * (x - prev));
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> cnt(n);
        long long res = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            cin >> cnt[i];
            if (cnt[i] > cur) 
                res += cnt[i] - cur;
            cur = cnt[i];
        }
        
        cout << res - 1 << endl;
    }
    return 0;
}

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x, y = min(a), max(a)
	res = []
	while x != y:
		res.append(x % 2)
		x = (x + res[-1]) // 2
		y = (y + res[-1]) // 2
	print(len(res))
	if len(res) <= n:
		print(*res)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &it : a) cin >> it;
    
    vector<int> pref(n), suf(n);
    for (int i = 0; i < n; ++i) {
        pref[i] = a[i] + (n - i - 1);
        suf[i] = a[i] + i;
    }
    for (int i = 1; i < n; ++i) {
        pref[i] = max(pref[i], pref[i - 1]);
    }
    for (int i = n - 2; i >= 0; --i) {
        suf[i] = max(suf[i], suf[i + 1]);
    }
    
    int ans = 2e9;
    for (int i = 0; i < n; ++i) {
        int cur = a[i];
        if (i > 0) cur = max(cur, pref[i - 1]);
        if (i + 1 < n) cur = max(cur, suf[i + 1]);
        ans = min(ans, cur);
    }
    
    cout << ans << endl;
    
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
const li INF = 1e18;
const int N = 555555;
 
int n;
int a[N];
vector<int> g[N];
li dp[N];
li ans;
 
void calc(int v, int p) {
  vector<li> sum(4, -INF);
  sum[0] = 0;
  for (int u : g[v]) if (u != p) {
    calc(u, v);
    for (int i = 3; i >= 0; --i) {
      sum[min(i + 1, 3)] = max(sum[min(i + 1, 3)], sum[i] + dp[u]);
    }
  }
  dp[v] = -INF;
  for (int j = 0; j < 4; ++j) {
    dp[v] = max(dp[v], sum[j] + (j == 1 ? 0 : a[v]));
    ans = max(ans, sum[j] + (j == 2 ? 0 : a[v]));
  }
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) g[i].clear();
    for (int i = 0; i < n - 1; ++i) {
      int x, y;
      cin >> x >> y;
      --x; --y;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    ans = 0;
    calc(0, -1);
    cout << ans << '\n';
  }
}

#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 all(a) (a).begin(), (a).end()
 
#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;
}
 
pt operator+ (const pt &a, const pt &b) {
	return {a.x + b.x, a.y + b.y};
}
pt operator- (const pt &a, const pt &b) {
	return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
	return a.x * 1ll * b.x + a.y * 1ll * b.y;
}
li operator %(const pt &a, const pt &b) {
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
int n;
vector<pt> old, nw;
 
inline bool read() {
	if(!(cin >> n))
		return false;
	old.resize(n);
	nw.resize(n);
	fore (i, 0, n) {
		old[i].x = i;
		cin >> old[i].y;
	}
	fore (i, 0, n) {
		nw[i].x = i;
		cin >> nw[i].y;
	}
	return true;
}
 
inline ld getTr(const pt &a, const pt &b) {
	pt tmp = b - a;
	pt v = {-tmp.y, tmp.x};
	ld c = v * a;
	ld y0 = (c - v.x * 0) / v.y;
	ld y1 = (c - v.x * li(n - 1)) / v.y;
	return (y0 + y1);
}
 
vector<pt> hull(const vector<pt> &ps, int l, int r) {
	vector<pt> h;
	fore (i, l, r) {
		while (sz(h) > 1 && (h[sz(h) - 1] - h[sz(h) - 2]) % (ps[i] - h[sz(h) - 1]) >= 0)
			h.pop_back();
		h.push_back(ps[i]);
	}
	return h;
}
 
inline void solve() {
	vector<ld> maxTr(n - 1, 0);
	fore (t, 0, 2) {
		auto h = hull(old, n / 2, n);
 
		auto best = [&](const pt &p) {
			int l = -1, r = sz(h) - 1;
			while (r - l > 1) {
				int mid = (l + r) >> 1;
				if ((h[mid] - p) % (h[mid + 1] - h[mid]) >= 0)
					l = mid;
				else
					r = mid;
			}
			return h[r].x;
		};
		
		vector<ld> bs(n / 2 + 1, 0);
		for (int i = n / 2 - 1; i >= 0; i--) {
			int j = best(old[i]);
			bs[i] = getTr(old[i], old[j]);
			bs[i] = max(bs[i], bs[i + 1]);
		}
		
		ld lans = 0;
		fore (i, 0, n / 2) {
			int j = best(nw[i]);
			lans = max(lans, getTr(nw[i], old[j]));
			maxTr[i] = max({maxTr[i], lans, bs[i + 1]});
		}
		
		reverse(all(old));
		reverse(all(nw));
		swap(old, nw);
		fore (i, 0, n)
			old[i].x = nw[i].x = i;
		
		reverse(all(maxTr));
	}
			
	maxTr.push_back(maxTr.back());
	cout << maxTr << 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(12);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    if y < x:
      print(x)
    else:
      print(y + max(0, y - x - k))

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> a;

inline void read() {
  cin >> n;
  a.clear();
  for (int i = 0; i < 2 * n; i++) {
      int x;
      cin >> x;
      a.pb(x);
  }
}
inline void solve() {
    sort(all(a));
    vector<pair<int, int> > pts;
    for (int i = 0; i < n; i++) {
        pts.pb(mp(a[i], a[i + n]));
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pts[i - 1].sc);
    }
    cout << ans << endl;
    for (int i = 0; i < n; i++) {
        cout << pts[i].ft << ' ' << pts[i].sc << endl;
    }
}
 
int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

n = int(input())
s = input().split()
ans = 0
cnt = [[0 for k in range(46)] for k in range(6)]
for y in s:
    cnt[len(y)][sum([int(c) for c in y])] += 1
for L in s:
    for lenr in range(len(L) % 2, len(L) + 1, 2):
        l = len(L) + lenr
        suml = sum([int(c) for c in L[:l // 2]])
        sumr = sum([int(c) for c in L[l // 2:]])
        if suml - sumr >= 0:
            ans += cnt[lenr][suml - sumr]
for R in s:
    for lenl in range(len(R) % 2, len(R), 2):
        l = len(R) + lenl
        suml = sum([int(c) for c in R[-l // 2:]])
        sumr = sum([int(c) for c in R[:-l // 2]])
        if suml - sumr >= 0:
            ans += cnt[lenl][suml - sumr]
print(ans)

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

const int LOG = 20;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  vector<array<int, 2>> t({{-1, -1}});
  auto add = [&](int x) {
    int v = 0;
    for (int i = LOG - 1; i >= 0; --i) {
      int j = (x >> i) & 1;
      if (t[v][j] == -1) {
        t[v][j] = t.size();
        t.push_back({-1, -1});
      }
      v = t[v][j];
    }
  };  
  for (int x : a) add(x);
  auto get = [&](int x) {
    int v = 0;
    for (int i = LOG - 1; i >= 0; --i) {
      int j = (x >> i) & 1;
      if (t[v][j ^ 1] != -1) j ^= 1;
      x ^= j << i;
      v = t[v][j];
    }
    return x;
  };
  for (int x = 0; x < n; ++x) {
    if (get(x) == n - 1) {
      for (int i : a) cout << (x ^ i) << ' ';
      break;
    }
  }
}

//

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct card{
  int x, y;
  card() {}
  card(int x, int y) : x(x), y(y) {}
};

void dfs(int v, const vector<int> &g, vector<int> &res, vector<char> &used){
  if (used[v]) return;
  used[v] = true;
  dfs(g[v], g, res, used);
  res[v] = -res[g[v]];
}

void solve(){
  vector<vector<card>> a(2);
  vector<vector<int>> prpos(2);
  forn(z, 2){
    int n;
    scanf("%d", &n);
    a[z].resize(n);
    forn(i, n) scanf("%d", &a[z][i].x);
    forn(i, n) scanf("%d", &a[z][i].y);
    sort(a[z].begin(), a[z].end(), [](const card &a, const card &b){
      return a.x > b.x;
    });
    prpos[z].resize(n + 1, -1);
    forn(i, n){
      if (prpos[z][i] == -1 || a[z][i].y > a[z][prpos[z][i]].y)
        prpos[z][i + 1] = i;
      else
        prpos[z][i + 1] = prpos[z][i];
    }
  }
  int n = a[0].size();
  vector<int> g(n + a[1].size());
  forn(z, 2) forn(i, a[z].size()){
    int cnt = lower_bound(a[z ^ 1].begin(), a[z ^ 1].end(), card(a[z][i].y, -1), [](const card &a, const card &b){
      return a.x > b.x;
    }) - a[z ^ 1].begin();
    g[i + z * n] = prpos[z ^ 1][cnt] == -1 ? -1 : prpos[z ^ 1][cnt] + (z ^ 1) * n;
  }
  vector<int> res(g.size());
  vector<char> used(g.size());
  forn(i, g.size()) if (g[i] == -1) res[i] = 1, used[i] = true;
  int w = 0, l = 0;
  forn(i, n){
    if (!used[i]) dfs(i, g, res, used);
    w += res[i] == 1;
    l += res[i] == -1;
  }
  printf("%d %d %d\n", w, n - l - w, l);
}

int main(){
  int t;
  scanf("%d", &t);
  while (t--) solve();
}

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int MOD = 1e9 + 7;
const int N = 40;

using mat = array<array<int, N>, N>;

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;
}

mat mul(mat x, mat y) {
  mat res;
  forn(i, N) forn(j, N) res[i][j] = 0;
  forn(i, N) forn(j, N) forn(k, N)
    res[i][j] = add(res[i][j], mul(x[i][k], y[k][j]));
  return res;
}

template<class T>
T binpow(T x, int y, T e) {
  T res = e;
  while (y) {
    if (y & 1) res = mul(res, x);
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, x, k;
    cin >> n >> x >> k;
    mat a, e;
    forn(i, N) forn(j, N) a[i][j] = (i < x && abs(i - j) <= k);
    forn(i, N) forn(j, N) e[i][j] = (i == j);
    mat b = binpow(a, n - 1, e);
    int ans = mul(x + k, binpow(2 * k + 1, n - 1, 1));
    forn(i, x) forn(j, x) ans = add(ans, -b[i][j]);
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(42);

struct node
{
  long long x;
  int y;
  int cnt;
  int sum;
  int push;
  node* l;
  node* r;
  node() {};
  node(long long x, int y, int cnt, int sum, int push, node* l, node* r) : x(x), y(y), cnt(cnt), sum(sum), push(push), l(l), r(r) {};
};

typedef node* treap;
typedef pair<treap, treap> ptt;

int getSum(treap t)
{
  return (t ? t->sum : 0);
}

int getCnt(treap t)
{
  return (t ? t->cnt : 0);
}

treap fix(treap t)
{
  if(!t) return t;
  int p = t->push;
  if(p != 0)
  {
    if(t->l) t->l->push += p;
    if(t->r) t->r->push += p;
    t->x += p;
    t->push = 0;
  }
  t->sum = getSum(t->l) + t->cnt + getSum(t->r);
  return t;
}

treap merge(treap a, treap b)
{
  a = fix(a);
  b = fix(b);
  if(!a) return b;
  if(!b) return a;
  if(a->y > b->y)
  {
    a->r = merge(a->r, b);
    return fix(a);
  }
  else
  {
    b->l = merge(a, b->l);
    return fix(b);
  }
}

bool hasKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return false;
  if(t->x == x) return true;
  if(t->x < x) return hasKey(t->r, x);
  return hasKey(t->l, x);
}

ptt splitKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return make_pair(t, t);
  if(t->x < x)
  {
    ptt p = splitKey(t->r, x);
    t->r = p.first;
    return make_pair(fix(t), p.second);
  }
  else
  {
    ptt p = splitKey(t->l, x);
    t->l = p.second;
    return make_pair(p.first, fix(t));
  }
}

long long kthMax(treap t, int k)
{
  t = fix(t);
  if(!t) return -1;
  int sumR = getSum(t->r);
  if(sumR >= k) return kthMax(t->r, k);
  if(sumR + t->cnt >= k) return t->x;
  return kthMax(t->l, k - sumR - t->cnt);
}

int getCntByKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return 0;
  if(t->x == x) return t->cnt;
  if(t->x > x) return getCntByKey(t->l, x);
  return getCntByKey(t->r, x);
}

treap increaseKey(treap t, long long x, int cnt)
{
  t = fix(t);
  if(!t) return t;
  if(t->x == x)
  {
    t->cnt += cnt;
  }
  else if(t->x > x)
  {
    t->l = increaseKey(t->l, x, cnt);
  }
  else
  {
    t->r = increaseKey(t->r, x, cnt);
  }
  return fix(t);
}

treap insert(treap t, long long x, int y, int cnt)
{
  t = fix(t);
  if(!t || t->y < y)
  {
    ptt p = splitKey(t, x);
    treap res = new node(x, y, cnt, cnt, 0, p.first, p.second);
    return fix(res);
  }
  if(t->x > x)
    t->l = insert(t->l, x, y, cnt);
  else
    t->r = insert(t->r, x, y, cnt);
  return fix(t);
}

treap insertMain(treap t, long long x, int cnt)
{
  if(hasKey(t, x))
    return increaseKey(t, x, cnt);
  else
    return insert(t, x, rnd(), cnt);
}

treap eraseKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return NULL;
  if(t->x > x)
  {
    t->l = eraseKey(t->l, x);
    return fix(t);
  }
  if(t->x < x)
  {
    t->r = eraseKey(t->r, x);
    return fix(t);
  }
  treap tnew = merge(t->l, t->r);
  delete t;
  return tnew;
}

ptt splitSum(treap t, int k)
{
  t = fix(t);
  if(!t) return make_pair(t, t);
  if(k == 0) return make_pair(t, treap(NULL));
  long long x = kthMax(t, k);
  int cnt = getCntByKey(t, x);
  t = eraseKey(t, x);
  ptt p = splitKey(t, x);
  k -= getSum(p.second);
  if(k > 0) p.second = merge(new node(x, rnd(), k, k, 0, NULL, NULL), p.second);
  if(k < cnt) p.first = merge(p.first, new node(x, rnd(), cnt - k, cnt - k, 0, NULL, NULL));
  return p;
}

long long minKey(treap t)
{
  t = fix(t);
  if(!t) return 1e18;
  if(t->l) return minKey(t->l);
  return t->x;
}

treap decreaseUpToKLargest(treap t, int k, int& res)
{
  if(!k) return t;
  t = fix(t);
  k = min(k, getSum(t));
  res = k;
  ptt p = splitSum(t, k);
  if(p.second)
  {
    p.second->push--;
    for(int i = 0; i < 2; i++)
    {
        long long x = minKey(p.second);
        int cntMin = getCntByKey(p.second, x);
        p.second = eraseKey(p.second, x);
        if(x != 0 && cntMin != 0)
          p.first = insertMain(p.first, x, cntMin);
    }
  }
  return merge(p.first, p.second);
}

void destroy(treap t)
{
  if(!t) return;
  if(t->l) destroy(t->l);
  if(t->r) destroy(t->r);
  delete t;
}

void solve()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<long long> r(n), b(n);
  for(int i = 0; i < n; i++) cin >> r[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  long long sum = 0;
  for(int i = 0; i < n; i++) sum += r[i] + b[i];
  long long flow = 0;
  treap t = NULL;
  for(int i = 0; i < n; i++)
  {
    long long d = min(r[i], b[i]);
    flow += d;
    r[i] -= d;
    b[i] -= d;
    if(s[i] == '0')
    {
      int add = 0;
      if(r[i] > 1e9) r[i] = 1e9;
      t = decreaseUpToKLargest(t, r[i], add);
      flow += add;
    }
    else
    {
      if(r[i] != 0) t = insertMain(t, r[i], 1);
    }
  }
  cout << sum - flow << 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>

using namespace std;

int n;

inline void read() {
	cin >> n;
}

inline void solve() {
	for (int x = 1; x <= 20; x++) {
	    for (int y = 1; y <= 20; y++) {
	        if (x + y >= n || x == y) continue;
	        int z = n - x - y;
	        if (z == x || z == y) continue;
	        if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) {
	            continue;
	        }
	        puts("YES");
	        cout << x << ' ' << y << ' ' << z << endl;
	        return;
	    }
	}
	puts("NO");
}

int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  auto dist = [](int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  };
 
  int t;
  cin >> t;
  while (t--) {
    int px, py, ax, ay, bx, by;
    cin >> px >> py >> ax >> ay >> bx >> by;
    double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by);
    double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by);
    double ab = dist(ax, ay, bx, by);
    double ans = 1e9;
    ans = min(ans, max(pa, oa));
    ans = min(ans, max(pb, ob));
    ans = min(ans, max({ab / 2, pa, ob}));
    ans = min(ans, max({ab / 2, pb, oa}));
    cout << setprecision(10) << fixed << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200000;

int t;

int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string s;
        long long pos;
        cin >> s >> pos;
        --pos;
        
        int curLen = s.size();
        vector <char> st;
        bool ok = pos < curLen;
        s += '$';
        
        for (auto c : s) {
            while (!ok && st.size() > 0 && st.back() > c) {
                pos -= curLen;
                --curLen;
                st.pop_back();
                
                if(pos < curLen) 
                    ok = true;
            }
            st.push_back(c);
        }
        
        cout << st[pos];
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

const int N = 300009;

int bp(int a, int n) {
    int res = 1;
    while(n > 0) {
        if (n & 1)
            res = (res * 1LL * a) % MOD;
        a = (a * 1LL * a) % MOD;
        n >>= 1;
    }
    return res;
}

int n, m;
string s;
int inv[N];

void upd(int &res, int x) {
    res = (res * 1LL * x) % MOD;
}

int main() {
    inv[1] = 1;
    for (int i = 2; i < N; ++i){
	    inv[i] = bp(i, MOD - 2);
    }
    
    cin >> n >> m >> s;
    
    int res = 1, k = n;
    bool isZero = false;
    for (int i = 0; i < s.size(); ++i) 
        if (s[i] == '?') {
            if (i == 0) {
                isZero = true;
            } else {
                upd(res, i);
            }
        }
    
    cout << (isZero? 0 : res) << endl;
    
    for(int i = 0; i < m; ++i) {
        int pos;
        char c;
        cin >> pos >> c;
        --pos;
        
        if (s[pos] == '?' && (c == '<' || c == '>')) {
            if (pos == 0)
                isZero = false;
            else
                upd(res, inv[pos]);
        } else if ((s[pos] == '<' || s[pos] == '>') && c == '?') {
            if (pos == 0)
                isZero = true;
            else
                upd(res, pos);
        }
        
        s[pos] = c;
        cout << (isZero? 0 : res) << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> a(n), b(m);
	forn(i, n) scanf("%d", &a[i]);
	forn(i, m) scanf("%d", &b[i]);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&a](int i, int j){
		return a[i] > a[j];
	});
	vector<vector<int>> mn(m, vector<int>(n + 2));
	forn(i, m){
		int r = 0;
		forn(l, n + 2){
			r = min(n + 1, max(r, l + 1));
			while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r;
			mn[i][l] = r;
		}
	}
	vector<int> dp(1 << m, n + 1);
	dp[0] = 0;
	vector<int> p(1 << m, -1);
	forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){
		dp[mask | (1 << i)] = mn[i][dp[mask]];
		p[mask | (1 << i)] = mask;
	}
	int mask = (1 << m) - 1;
	if (dp[mask] > n){
		puts("NO");
		return 0;
	}
	puts("YES");
	vector<vector<int>> ans(n);
	forn(_, m){
		int i = __builtin_ctz(mask ^ p[mask]);
		for (int j = dp[p[mask]]; j < dp[mask]; ++j)
			ans[i].push_back(ord[j]);
		mask = p[mask];
	}
	forn(i, m){
		printf("%d", int(ans[i].size()));
		for (int x : ans[i]) printf(" %d", x + 1);
		puts("");
	}
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3003;
 
int n;
int k[4];
vector<int> a[4];
 
struct segtree {
  int sz;
  int tot;
  vector<int> t, p;
  
  segtree(int sz) : sz(sz) {
    tot = 0;
    t = vector<int>(4 * sz);
    p = vector<int>(4 * sz);
    build(0, 0, sz);
  }
  
  void build(int v, int l, int r) {
    if (l + 1 == r) {
      t[v] = -l;
      return;
    }
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m);
    build(v * 2 + 2, m, r);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void push(int v) {
    if (p[v] == 0) return;
    if (v + 1 < 2 * sz) {
      t[v * 2 + 1] += p[v];
      p[v * 2 + 1] += p[v];
      t[v * 2 + 2] += p[v];
      p[v * 2 + 2] += p[v];
      p[v] = 0;
    }
  } 
  
  void upd(int v, int l, int r, int L, int R, int x) {
    if (L >= R) return;
    if (l == L && r == R) {
      t[v] += x;
      p[v] += x;
      return;
    }
    push(v);
    int m = (l + r) / 2;
    upd(v * 2 + 1, l, m, L, min(m, R), x);
    upd(v * 2 + 2, m, r, max(L, m), R, x);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void upd(int pos, int x) { 
    tot += x;
    upd(0, 0, sz, max(0, pos), sz, x);
  }
  
  int get(int v, int l, int r, int L, int R) {
    if (L >= R) return -1e9;
    if (l == L && r == R) return t[v];
    push(v);
    int m = (l + r) / 2;
    return max(
      get(v * 2 + 1, l, m, L, min(m, R)),
      get(v * 2 + 2, m, r, max(L, m), R)
    );
  }
  
  int get(int L) {
    return get(0, 0, sz, max(0, L), sz);
  }
  
  int getBad(int v, int l, int r) {
    if (t[v] <= 0) return -1;
    if (l + 1 == r) return l;
    push(v);
    int m = (l + r) / 2;
    if (t[v * 2 + 1] > 0) {
      return getBad(v * 2 + 1, l, m);
    } else {
      return getBad(v * 2 + 2, m, r);
    }
  }
  
  int getBad() {
    return getBad(0, 0, sz);
  }
};  
 
int main() {
  cin >> n;
  int sz = 1;
  for (int i = 0; i < n; ++i) {
    int t, s;
    cin >> t >> s;
    a[t].push_back(s);
    sz = max(sz, s + 1);
  }
  for (int t = 1; t < 4; ++t) {
    sort(a[t].begin(), a[t].end());
    k[t] = a[t].size();
  }
  reverse(a[2].begin(), a[2].end());
  int ans = 1e4;
  for (int len = 1; len <= k[2] + k[3] + 1; ++len) {
    segtree L(sz), R(sz);
    multiset<int> used;
    for (int x : a[1]) L.upd(x, +1);
    for (int x : a[2]) R.upd(x, +1);
    for (int x : a[3]) {
      L.upd(x - len, +1);
      if (L.t[0] <= 0) {
        used.insert(x - len);
      } else {
        L.upd(x - len, -1);
        L.upd(x, +1);
        R.upd(x, +1);
      }
    }
    for (int i = 0; i <= k[2]; ++i) {
      if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len)
        ans = min(ans, n + (k[3] - (int)used.size()) + 2); 
      if (i == k[2]) break;
      R.upd(a[2][i], -1);
      L.upd(a[2][i] - len, +1);
      int pos;
      while ((pos = L.getBad()) != -1) {
        auto it = used.upper_bound(pos);
        if (it == used.begin()) break;
        --it;
        L.upd(*it, -1);
        L.upd(*it + len, +1);
        R.upd(*it + len, +1);
        used.erase(it);
      }
    }
  }
  if (ans == 1e4) ans = -1;
  cout << ans << '\n';
}