t = int(input())
for tt in range(t):
    n = int(input())
    ans = 0
 
    def dig_sum(n):
        s = str(n)
        sum = 0
        for j in s:
            sum += ord(j) - ord('0')
        return sum
 
    for i in range(n, n + 200):
        if i - dig_sum(i) == n:
            ans += 1
    print(ans)

#include <bits/stdc++.h>
 
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) int(a.size())
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
using namespace std;
 
const int mod = 998244353;
 
const int N = 1e6 + 228;
 
pair<int, int> zero = {-1, N};
 
 
void solve() {
    int n;
    cin >> n;
    map<int, int> pos;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        pos[a] = i;
    }
    int lst = -1;
    vector<int> b(n);
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) {
        if (lst > pos[b[i]]) {
            cout << "NO\n";
            return;
        }
        lst = pos[b[i]];
    }
    cout << "YES\n";
}
 
int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t = 1;
    cin >> t;
    while (t--) solve();
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve(){
	int p, q;
	cin >> p >> q;
	if (p < q && min(p / 2, q / 3) >= q - p){
		cout << "Bob\n";
	}
	else{
		cout << "Alice\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 SQ = 500;
 
void solve(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
 
  int ans = 0;
 
  for (int i = 0; i < n; i++){
    if (a[i] >= SQ){
      for (int j = 1; i + a[i] * j < n; j++){
        if (a[i + a[i] * j] == j){
          ans++;
        }
      }
      for (int j = 1; i - a[i] * j >= 0; j++){
        if (a[i - a[i] * j] == j){
          ans++;
        }
      }
    }
    else{
      for (int j = 1; i + a[i] * j < n && j < SQ; j++){
        if (a[i + a[i] * j] == j){
          ans++;
        }
      }
    }
  }
 
  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 int long long
 
const int INF = 1'000'000'007;
 
vector<int> ask(int k){
	cout << "? " << k << endl;
	int l;
	cin >> l;
	if (l == -1){
		exit(0);
	}
	vector<int> res(l);
	for (int i = 0; i < l; i++){
		cin >> res[i];
	}
	return res;
}
 
void solve(){
	int n;
	cin >> n;
 
	vector<pair<int, int>> edges;
 
	for (int i = 0; i < n; i++){
		int prev = -1;
		while(1){
			int l = 1, r = (1 << 30);
			while(l <= r){
				int m = l + (r - l) / 2;
				auto path = ask(m);
				if (!path.empty() && path[0] < i + 1){
					l = m + 1;
					continue;
				}
				if (path.empty() || path[0] > i + 1 || (path.size() > 1 && path[1] > prev)){
					r = m - 1;
				}
				else{
					l = m + 1;
				}
			}
 
			auto path = ask(l);
			if (path.size() > 1){
				edges.emplace_back(path[0], path[1]);
				prev = path[1];
			}
			else{
				break;
			}
		}
	}
 
	cout << "! " << edges.size() << endl;
	for (auto [u, v] : edges){
		cout << u << ' ' << v << endl;
	}
}
 
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;
 
vector<int> ask(int k){
	cout << "? " << k << endl;
	int cnt;
	cin >> cnt;
	vector<int> res(cnt);
	for (int i = 0; i < cnt; i++){
		cin >> res[i];
		res[i]--;
	}
	return res;
}
 
void solve(){
	int n;
	cin >> n;
 
	int m = 0;
	vector<vector<int>> g(n);
	vector<int> cnt(n, -1);
 
	function<void(int)> calc = [&](int v){
		if (cnt[v] != -1){
			return;
		}
		cnt[v] = 1;
		for (int to : g[v]){
			calc(to);
			cnt[v] += cnt[to];
		}
	};
 
	vector<int> prev = {0};
	int k = 2;
 
	while(1){
		auto cur = ask(k);
		if (cur.size() == 0){
			break;
		}
		int com_pref = 0;
		for (int i = 0; i < min(prev.size(), cur.size()); i++){
			if (prev[i] != cur[i]){
				break;
			}
			com_pref++;
		}
		if (prev.size() > com_pref){
			calc(prev[com_pref]);
		}
 
		if (com_pref > 0){
			g[cur[com_pref - 1]].push_back(cur[com_pref]);
			m++;
		}
		if (cnt[cur[com_pref]] == -1){
			k++;
		}
		else{
			k += cnt[cur[com_pref]];
		}
		prev = cur;
	}
 
	cout << "! " << m << endl;
	for (int i = 0; i < n; i++){
		for (int to : g[i]){
			cout << i + 1 << ' ' << to + 1 << endl;
		}
	}
}
 
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;
 
#define int long long
 
const int INF = 1'000'000'007;
 
void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
 
	vector<int> stay(n);
 
	auto delete_cbs = [&](char open, char close){
		vector<int> st;
		for (int i = 0; i < n; i++){
			if (s[i] == close){
				if (!st.empty() && s[st.back()] == open){
					st.pop_back();
				}
				else{
					st.push_back(i);
				}
			}
			else if (s[i] == open){
				st.push_back(i);
			}
		}
		for (int x : st){
			stay[x] = 1;
		}
	};
 
	delete_cbs('(', ')');
	delete_cbs('[', ']');
 
	int last_open = 0;
	int cnt_open = 0, cnt_close = 0;
	int ans = 1;
 
	for (int i = 0; i < n; i++){
		if (!stay[i]){
			continue;
		}
		if (s[i] == '(' || s[i] == '['){
			cnt_open++;
			last_open = 1;
		}
		else{
			cnt_close++;
			if (last_open){
				ans = 0;
			}
			last_open = 0;
		}
	}
	if (cnt_open % 2 == 0 || cnt_close % 2 == 0){
		ans = 0;
	}
	ans += (cnt_open + cnt_close) / 2;
	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;
 
template <typename T>
struct SparseTable{
	int n, r;
	vector<vector<T>> t;
	void build(vector<T> &a) {
		n = a.size();
		r = 32 - __builtin_clz(n);
		t.resize(r, vector<T>(n + 1));
		for(int i = 1; i <= n; ++i) t[0][i] = a[i - 1];
		for(int k = 1; k < r; ++k) {
			for(int i = 1; i + (1 << k) - 1 <= n; ++i) {
				t[k][i] = f(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
			}
		}
	}
 
	T query(int l, int r) {
		int k = 31 - __builtin_clz(r - l + 1);
		return f(t[k][l], t[k][r - (1 << k) + 1]);
	}
 
	inline T f(T x, T y){
		return min(x, y);
	}
};
 
struct SuffixArray{
    int n;
    vector<int> sa;
    vector<int> lcp;
 
    vector<int> _s;
    vector<int> _inv_sa;
    SparseTable<int> _st_lcp;
 
    SuffixArray(){}
 
    void build(const string& s){
        _s.assign(s.size(), 0);
        for (int i = 0; i < s.size(); i++){
            _s[i] = s[i];
        }
        _build(_s);
        _build_lcp_array();
        _st_lcp.build(lcp);
    }
 
    void build(const vector<int>& s){
        _s.assign(s.size(), 0);
        for (int i = 0; i < s.size(); i++){
            _s[i] = s[i];
        }
        _build(_s);
        _build_lcp_array();
        _st_lcp.build(lcp);
    }
 
    void _build(const vector<int>& s){
        map<int, int> mp;
        for (int ch : s){
            mp[ch] = 0;
        }
        int cc = 1;
        for (auto& [key, val]: mp){
            val = cc++;
        }
 
        n = s.size() + 1;
        vector<int> c(n);
        sa.assign(n, 0);
 
        for (int i = 0; i < s.size(); i++){
            c[i] = mp[s[i]];
            sa[i] = i;
        }
        c[n - 1] = 0;
        sa[n - 1] = n - 1;
 
        for (int i = 1; (i >> 1) < n; i <<= 1){
            if (i != 1){
                for (int j = 0; j < n; j++){
                    sa[j] = (sa[j] - (i >> 1) + n) % n;
                }
            }
            vector<int> cnt(n);
            for (int j = 0; j < n; j++){
                cnt[c[sa[j]]]++;
            }
            int su = 0;
            for (int j = 0; j < n; j++){
                su += cnt[j];
                cnt[j] = su - cnt[j];
            }
            vector<int> new_sa(n);
            for (int j = 0; j < n; j++){
                new_sa[cnt[c[sa[j]]]++] = sa[j];
            }
            sa.swap(new_sa);
 
            if (i != 1){
                vector<int> new_c(n);
                new_c[sa[0]] = 0;
                for (int j = 1; j < n; j++){
                    if (c[sa[j]] > c[sa[j - 1]] || c[(sa[j] + (i >> 1)) % n] > c[(sa[j - 1] + (i >> 1)) % n]){
                        new_c[sa[j]] = new_c[sa[j - 1]] + 1;
                    }
                    else{
                        new_c[sa[j]] = new_c[sa[j - 1]];
                    }
                }
                c.swap(new_c);
            }
        }
    }
 
    void _build_lcp_array(){
        lcp.assign(n - 1, 0);
        _inv_sa.assign(n, 0);
        for (int i = 0; i < n; i++){
            _inv_sa[sa[i]] = i;
        }
        for (int i = 0; i < n; i++){
            if (_inv_sa[i] == n - 1){
                continue;
            }
            lcp[_inv_sa[i]] = 0;
            if (i > 0 && _inv_sa[i - 1] != n - 1){
                lcp[_inv_sa[i]] = max(0, lcp[_inv_sa[i - 1]] - 1);
            }
 
            int len = min(n - 1 - i, n - 1 - sa[_inv_sa[i] + 1]);
            while (lcp[_inv_sa[i]] < len && _s[i + lcp[_inv_sa[i]]] == _s[sa[_inv_sa[i] + 1] + lcp[_inv_sa[i]]]){
                lcp[_inv_sa[i]]++;
            }
        }
    }
 
    int get_lcp(int i, int j){
        assert(i != j);
        i = _inv_sa[i];
        j = _inv_sa[j];
        if (i > j){
            swap(i, j);
        }
        j--;
        return _st_lcp.query(i + 1, j + 1);
    }
};
 
void solve(){
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
 
    string all = s + "%" + t;
    SuffixArray suff_array;
    suff_array.build(all);
    all += '#';
 
    vector<int> from_s;
    for (int i = 0; i < n + m + 2; i++){
        if (suff_array.sa[i] < n){
            from_s.push_back(i);
        }
    }
 
    function<pair<int, int>(int, int, char, int)> compare_suff = [&](int start, int pos, char ch, int suff_num){
        if (suff_num == 0 || suff_num > n){
            return pair<int, int>{1, 0};
        }
        pos -= start;
        suff_num--;
        suff_num = suff_array.sa[from_s[suff_num]];
        
        int lcp1 = suff_array.get_lcp(suff_num, n + 1 + start);
        if (lcp1 < pos){
            char ch1 = all[suff_num + lcp1];
            char ch2 = all[n + 1 + start + lcp1];
            if (ch1 < ch2){
                return pair<int, int>{1, lcp1};
            }
            else{
                return pair<int, int>{-1, lcp1};
            }
        }
        else if (lcp1 > pos){
            char ch1 = all[suff_num + pos];
            char ch2;
            int len = pos;
            if (ch1 != ch){
                ch2 = ch;
            }
            else{
                len = lcp1;
                ch1 = all[suff_num + lcp1];
                ch2 = all[n + 1 + start + lcp1];
            }
            if (ch1 < ch2){
                return pair<int, int>{1, len};
            }
            else{
                return pair<int, int>{-1, len};
            }
        }
 
        char ch1 = all[suff_num + lcp1];
        char ch2 = ch;
        if (ch1 < ch2){
            return pair<int, int>{1, pos};
        }
        else if (ch1 > ch2){
            return pair<int, int>{-1, pos};
        }
 
        int lcp2 = suff_array.get_lcp(suff_num + lcp1 + 1, n + 1 + start + lcp1 + 1);
 
        ch1 = all[suff_num + lcp1 + 1 + lcp2];
        ch2 = all[n + 1 + start + lcp1 + 1 + lcp2];
 
        if (ch1 < ch2){
            return pair<int, int>{1, pos + 1 + lcp2};
        }
        else{
            return pair<int, int>{-1, pos + 1 + lcp2};
        }
    };
 
    function<int(int, int, char)> get_max_len = [&](int start, int pos, char ch){
        int suff_len = n + 1 + start;
 
        int l = 0, r = from_s.size();
        while(l <= r){
            int m = l + (r - l) / 2;
            if (compare_suff(start, pos, ch, m).first == -1){
                r = m - 1;
            }
            else{
                l = m + 1;
            }
        }
        int res = 0;
        res = max(res, compare_suff(start, pos, ch, l - 1).second);
        res = max(res, compare_suff(start, pos, ch, l).second);
        return res;
    };
 
    int ans = 0;
    int start = 0;
    int pred = -1;
 
    for (int i = 0; i < m; i++){
        int mx_len = 0;
        for (char ch = 'a'; ch <= 'z'; ch++){
            mx_len = max(mx_len, get_max_len(start, i, ch));
        }
        pred = max(pred, mx_len);
        if (mx_len < i - start + 1){
            ans++;
            start += pred;
            pred = -1;
            i = start - 1;
            continue;
        }
    }
    if (start != m){
        ans++;
    }
 
    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>
 
#define int long long
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
 
vector<pair<int, int>> theSolve(int n, int m) {
  if (m == 1 || m == 2 || m == 4 || m == 6) {
    return {};
  }
  if (m == 12) {
    vector<pair<int, int>> e;
    for (int x = 1; x <= 6; x++) {
      for (int y = x + 1; y <= 6; y++) {
        if (max(x, y) >= 4) {
          e.pb({x, y});
        }
      }
    }
    return e;
  }
  if (n == 6 && m == 11) {
    return {{1, 2},
            {1, 3},
            {2, 4},
            {2, 5},
            {2, 6},
            {3, 4},
            {3, 5},
            {3, 6},
            {4, 5},
            {4, 6},
            {5, 6}};
  }
  if (n == 8 && m == 22) {
    vector<pair<int, int>> e;
    for (int v = 1; v <= 7; v++) {
      for (int u = v + 1; u <= 7; u++) {
        e.pb({v, u});
      }
    }
    e.pb({7, 8});
    return e;
  }
  if (n == 10 && m == 39) {
    vector<pair<int, int>> e;
    for (int x = 1; x <= n - 1; x++) {
      for (int y = x + 1; y <= n - 1; y++) {
        e.pb({x, y});
      }
    }
    for (int x = 1; x <= 3; x++) {
      e.pb({n, x});
    }
    return e;
  }
  vector<pair<int, int>> edges;
  if (n % 2 == 1) {
    while (m <= (n - 2) * (n - 3) / 2) {
      n -= 2;
    }
    int q = (2 * m) / n, r = (2 * m) % n;
    if (q % 2 == 0) {
      for (int v = 0; v < n; v++) {
        for (int p = 0; p < q / 2; p++) {
          int u = (v + 1 + p) % n;
          edges.pb({v + 1, u + 1});
        }
      }
      for (int v = 0; v < r / 2; v++) {
        edges.pb({v + 1, (v + n / 2) % n + 1});
      }
    } else {
      int d = (n - r) / 2;
      for (int v = 0; v < n; v++) {
        for (int p = 0; p < (q + 1) / 2; p++) {
          if (v % 2 == 0 && p == 0 && d) {
            d--;
            continue;
          }
          int u = (v + 1 + p) % n;
          edges.pb({v + 1, u + 1});
        }
      }
    }
    return edges;
  }
 
  int rest = n * (n - 1) / 2 - m;
  if (rest == 0 || rest == 1 || rest == 2 || rest == 4 || rest == 6) {
    return {};
  }
  if (m <= (n - 1) * (n - 2) / 2) {
    return theSolve(n - 1, m);
  }
  vector<pair<int, int>> inv_e = theSolve(n - 1, n * (n - 1) / 2 - m);
  for (auto &p : inv_e) {
    if (p.first > p.second) {
      swap(p.first, p.second);
    }
  }
  sort(all(inv_e));
  int i = 0;
  vector<pair<int, int>> e;
  for (int v = 1; v <= n; v++) {
    for (int u = v + 1; u <= n; u++) {
      if (i < (int) inv_e.size() && inv_e[i] == (pair<int, int>) {v, u}) {
        i++;
        continue;
      }
      e.pb({v, u});
    }
  }
  return e;
}
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> e = theSolve(n, m);
  if (e.empty()) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
    for (auto &[a, b] : e) {
      cout << a << ' ' << b << '\n';
    }
  }
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
void solve(){
	int x;
	cin >> x;
	int ans = 0;
	int a1 = 0, a2 = 0, a3 = 0;
	while(min({a1, a2, a3}) < x){
		if (a1 <= a2 && a1 <= a3){
			a1 = min(a2, a3) * 2 + 1;
		}
		else if (a2 <= a1 && a2 <= a3){
			a2 = min(a1, a3) * 2 + 1;
		}
		else{
			a3 = min(a1, a2) * 2 + 1;
		}
		ans++;
	}
	cout << ans << '\n';
}
 
signed main()
{
	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();
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(m);
 
	for (int i = 0; i < m; i++){
		for (int j = 0; j < 3; j++){
			int x;
			cin >> x;
			a[i].emplace_back(x);
		}
		sort(a[i].begin(), a[i].end());
	}

	vector<int> fib(n + 5);
	fib[0] = 1;
	fib[1] = 2;
	for (int i = 2; i < n + 1; i++){
		fib[i] = fib[i - 1] + fib[i - 2];
	}
 
	for (int i = 0; i < m; i++){
		if (a[i][0] >= fib[n - 1] && a[i][1] >= fib[n - 1] && a[i][2] >= fib[n]){
			cout << '1';
		}
		else{
			cout << '0';
		}
	}
	cout << '\n';
}
 
signed main()
{
	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();
	}
	return 0;
}

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    i = 0
    ans = 10**18
    while i < n:
        j = i
        while j < n and a[j] == a[i]:
            j += 1
        ans = min(ans, (i + n - j) * a[i])
        i = j
    print(ans)

#include<bits/stdc++.h>
 
using namespace std;
 
void solve(){
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	for (int i = 0; i < m; i++){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	vector<vector<int>> ans(n, vector<int> (6));
 
	for (int i = 0; i < n; i += 2){
		if (i + 1 == n){
			for (int j = 0; j < 6; j++){
				if (j % 2 == 0){
					ans[i][j] = a[i / 2];
				}
				else{
					ans[i][j] = a[m - i / 2 - 1];
				}
			}
		}
		else{
			for (int j = 0; j < 6; j++){
				if (j % 2 == 0){
					ans[i][j] = a[i / 2];
					ans[i + 1][j] = a[m - i / 2 - 1];
				}
				else{
					ans[i][j] = a[m - i / 2 - 1];
					ans[i + 1][j] = a[i / 2];
				}
			}
		}
	}
 
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 6; j++){
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
}
 
signed main()
{
	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();
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve(){
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<vector<set<int>>> st(3, vector<set<int>> (3));
	for (int i = 0; i < q; i++){
		char x, y;
		cin >> x >> y;
		st[x - 'a'][y - 'a'].insert(i);
	}

	for (int i = 0; i < n; i++){
		if (s[i] == 'a'){
			continue;
		}
		
		if (s[i] == 'b'){
			if (!st[1][0].empty()){
				st[1][0].erase(st[1][0].begin());
				s[i] = 'a';
				continue;
			}
			if (!st[1][2].empty()){
				auto ind = *st[1][2].begin();
				auto lb = st[2][0].lower_bound(ind);
				if (lb != st[2][0].end()){
					st[1][2].erase(ind);
					st[2][0].erase(lb);
					s[i] = 'a';
					continue;
				}
			}
		}

		if (s[i] == 'c'){
			if (!st[2][0].empty()){
				st[2][0].erase(st[2][0].begin());
				s[i] = 'a';
				continue;
			}
			if (!st[2][1].empty()){
				auto ind = *st[2][1].begin();
				st[2][1].erase(ind);
				s[i] = 'b';
				auto lb = st[1][0].lower_bound(ind);
				if (lb != st[1][0].end()){
					st[1][0].erase(lb);
					s[i] = 'a';
				}
			}
		}
	}

	cout << s << '\n';
}
 
signed main()
{
	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();
	}
	return 0;
}

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

#define int long long
 
void solve(){
	int p, s;
	cin >> p >> s;

	if (p > 4 * s){
		cout << "-1\n";
		return;
	}
	if (p > 2 * s){
		for (int i = 1; i <= 50000; i++){
			if (p * i == (2 + 2 * i) * s){
				cout << i << '\n';
				for (int j = 0; j < i; j++){
					cout << "0 " << j << '\n';
				}
				return;
			}
		}
		cout << "-1\n";
		return;
	}

	int k = 0;
	while(p > 2){
		p -= 2;
		s -= 1;
		k++;
	}

	if (p == 2){
		cout << 4 * s * s + 4 * s * k << '\n';
		for (int i = 0; i < 2 * s; i++){
			for (int j = 0; j < 2 * s; j++){
				cout << i << ' ' << j << '\n';
			}
		}
		for (int i = 0; i < 4 * s * k; i++){
			cout << 0 << ' ' << 2 * s + i << '\n';
		}
	}
	else{
		cout << 16 * s * s + 16 * s * k << '\n';
		for (int i = 0; i < 4 * s; i++){
			for (int j = 0; j < 4 * s; j++){
				cout << i << ' ' << j << '\n';
			}
		}
		for (int i = 0; i < 16 * s * k; i++){
			cout << 0 << ' ' << 4 * s + i << '\n';
		}
	}
}
 
signed main()
{
	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();
	}
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
struct PersistentSegmentTree{
	#define _null -1
	struct Node{
		int l, r;
		int val;
		Node(): l(-1), r(-1), val(_null) {}
	};
	vector<Node> data;
	vector<int> roots;
	PersistentSegmentTree(){}
 
	inline void copy(int x, int y){
		data[x].l = data[y].l;
		data[x].r = data[y].r;
		data[x].val = data[y].val;
	}
 
	int build(int v, int l, int r, vector<int>& a){
		if (data.size() == v){
			data.emplace_back();
		}
		if (l == r){
			data[v].val = a[l];
			return v;
		}
		int m = (l + r) / 2;
		data[v].l = build(data.size(), l, m, a);
		data[v].r = build(data.size(), m + 1, r, a);
		data[v].val = max(data[data[v].l].val, data[data[v].r].val);
		return v;
	}
 
	int update(int v, int l, int r, int pos, int val){
		int new_v = data.size();
		data.emplace_back();
		copy(new_v, v);
		if (l == r){
			data[new_v].val = val;
			return new_v;
		}
		int m = (l + r) / 2;
		if (pos <= m){
			data[new_v].l = update(data[v].l, l, m, pos, val);
		}
		else{
			data[new_v].r = update(data[v].r, m + 1, r, pos, val);
		}
		data[new_v].val = max(data[data[new_v].l].val, data[data[new_v].r].val);
		return new_v;
	}
 
	int get(int v, int l, int r, int ql, int qr){
		if (ql > qr){
			return _null;
		}
		if (l == ql && r == qr){
			return data[v].val;
		}
		int m = (l + r) / 2;
		return max(get(data[v].l, l, m, ql, min(qr, m)), 
			get(data[v].r, m + 1, r, max(ql, m + 1), qr));
	}
};
 
void solve(){
	int n;
	cin >> n;
 
	vector<int> p(n);
	for(int i = 0; i < n; i++){
		cin >> p[i];
		p[i]--;
	}
 
	vector<pair<int,int>> p2(n);
	for (int i = 0; i < n; i++){
		p2[i] = {p[i], i};
	}
	sort(p2.begin(), p2.end());
 
	vector<tuple<int,int,int,int>> seg;
	set<pair<int,int>> st;
 
	st.insert({-2, -2});
	st.insert({n + 1, n + 1});
 
	for (int i = 0; i < n; i++){
		auto [val, ind] = p2[i];
		auto up = st.lower_bound(pair{ind, -1});
		auto down = (--st.lower_bound(pair{ind, -1}));
 
		int l, r;
 
		if (down->second == ind - 1 && up->first == ind + 1){
			l = down->first, r = up->second;
			st.erase(up);
			st.erase(down);
		}
		else if (down->second == ind - 1){
			l = down->first, r = down->second + 1;
			st.erase(down);
		}
		else if (up->first == ind + 1){
			l = up->first - 1, r = up->second;
			st.erase(up);
		}
		else{
			l = ind, r = ind;
		}
		st.insert({l, r});
 
		up = st.lower_bound(pair{l + 1, -1});
		down = (--st.lower_bound(pair{l, -1}));
 
		if (l > 0){
			seg.emplace_back(max(0, down->second + 1), l - 1, r, i * 2);
		}
		if (r < n - 1){
			seg.emplace_back(l, r, min(n - 1, up->first - 1), i * 2 + 1);
		}
	}
 
	sort(seg.begin(), seg.end());
 
	vector<tuple<int,int,int>> seg2;
	for (int i = 0; i < seg.size(); i++){
		auto [l1, r1, r2, ind] = seg[i];
		seg2.emplace_back(r1 + 1, r2, ind);
	}
	sort(seg2.begin(), seg2.end());
 
	vector<int> pos(2 * n, -1);
	for (int i = 0; i < seg2.size(); i++){
		auto [l, r, ind] = seg2[i];
		pos[ind] = i;
	}
 
	set<pair<int,int>> open_left_segs;
 
	vector<int> cur(2 * n, -1);
	PersistentSegmentTree tree;
	tree.roots.emplace_back(tree.build(0, 0, 2 * n - 1, cur));
 
	vector<int> T(n, -1);
	int u = 0;
	for (int i = 0; i < n; i++){
		while(u < seg.size() && get<0>(seg[u]) <= i){
			auto [l1, r1, r2, ind] = seg[u];
			open_left_segs.insert({r1, pos[ind]});
			tree.roots.emplace_back(tree.update(tree.roots.back(), 0, 2 * n - 1, pos[ind], r2));
			u++;
		}
		while(!open_left_segs.empty() && open_left_segs.begin()->first < i){
			auto [r, ind] = *open_left_segs.begin();
			open_left_segs.erase(open_left_segs.begin());
			tree.roots.emplace_back(tree.update(tree.roots.back(), 0, 2 * n - 1, ind, -1));
		}
		T[i] = tree.roots.back();
	}
 
	int q;
	cin >> q;
	for (int i = 0; i < q; i++){
		if (i % 10 == 0){
			cout.flush();
		}
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		auto lb = lower_bound(seg2.begin(), seg2.end(), tuple{l + 1, -1, -1});
		if (lb == seg2.end()){
			cout << "NO\n";
			continue;
		}
		auto lb2 = lower_bound(seg2.begin(), seg2.end(), tuple{r + 1, -1, -1});
 
		int val;
		if (lb2 == seg2.end()){
			val = tree.get(T[l], 0, 2 * n - 1, pos[get<2>(*lb)], 2 * n - 1);
		}
		else{
			val = tree.get(T[l], 0, 2 * n - 1, pos[get<2>(*lb)], pos[get<2>(*lb2)] - 1);
		}
		cout << (val >= r ? "YES\n" : "NO\n");
	}
	cout.flush();
}
 
signed main()
{
	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();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int LOGN = 18;

struct solver{
    int n;
    vector<int> p;

    solver(const vector<int> &p) : p(p){
        n = p.size();
        build();
    }

    vector<int> nxtmn, nxtmx;

    vector<vector<int>> up;
    vector<vector<int>> mx;

    void build(){
        nxtmx.resize(n);
        vector<int> stmn, stmx;
        for (int i = n - 1; i >= 0; --i){
            while (!stmx.empty() && p[stmx.back()] < p[i])
                stmx.pop_back();
            nxtmx[i] = (stmx.empty() ? n : stmx.back());
            stmx.push_back(i);
        }
        vector<vector<int>> qr(n + 1);
        forn(i, n) qr[nxtmx[i]].push_back(i);
        nxtmn.assign(n, n);
        for (int i = n - 1; i >= 0; --i){
            while (!stmn.empty() && p[stmn.back()] > p[i])
                stmn.pop_back();
            stmn.push_back(i);
            for (int j : qr[i]){
                int l = 0, r = int(stmn.size()) - 1;
                while (l <= r){
                    int m = (l + r) / 2;
                    if (p[stmn[m]] < p[j]){
                        nxtmn[j] = stmn[m];
                        l = m + 1;
                    }
                    else{
                        r = m - 1;
                    }
                }
            }
        }
        up.assign(n + 1, vector<int>(LOGN));
        mx.assign(n + 1, vector<int>(LOGN));
        forn(i, n){
            up[i][0] = nxtmx[i];
            mx[i][0] = nxtmn[i];
        }
        up[n][0] = n;
        mx[n][0] = 0;
        for (int j = 1; j < LOGN; ++j) forn(i, n + 1){
            up[i][j] = up[up[i][j - 1]][j - 1];
            mx[i][j] = max(mx[i][j - 1], mx[up[i][j - 1]][j - 1]);
        }
    }

    bool query(int l, int r){
        int v = l;
        for (int i = LOGN - 1; i >= 0; --i){
            if (up[v][i] >= r) continue;
            if (mx[v][i] >= r) return true;
            v = up[v][i];
        }
        return false;
    }
};

int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int>> p(2, vector<int>(n));
    forn(i, n){
        cin >> p[0][i];
        --p[0][i];
    }
    p[1] = p[0];
    reverse(p[1].begin(), p[1].end());
    solver p0(p[0]);
    solver p1(p[1]);
    int m;
    cin >> m;
    forn(i, m){
		if (i % 10 == 0){
			cout.flush();
		}
        int l, r;
        cin >> l >> r;
        --l; -- r;
        bool ans = p0.query(l, r + 1) || p1.query(n - r - 1, n - l);
        cout << (ans ? "YES\n" : "NO\n");
    }
    cout.flush();
}

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << n * 2 << "\n";
    }
    return 0;
}

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

void solve(){
    int n, k, x;
    cin >> n >> k >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    if (accumulate(a.begin(), a.end(), 0ll) * k < x){
        cout << 0 << '\n';
        return;
    }

    int l = 1, r = n * k;
    while(l <= r){
        int m = l + (r - l) / 2;
        int cnt_a = (n * k - m + 1) / n;
        int suff = (n * k - m + 1) % n;
        int sum = cnt_a * accumulate(a.begin(), a.end(), 0ll);
        for (int i = n - suff; i < n; i++){
            sum += a[i];
        }
        if (sum < x){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }

    cout << r << '\n';
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	while(t--){
	    solve();
	}
}

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

void solve(){
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++){
        cin >> p[i];
        p[i]--;
    }

    set<int> X;
    for (int i = 0; i < n; i++){
        int d;
        cin >> d;
        d--;
        while(!X.contains(d)){
            X.insert(d);
            d = p[d];
        }
        cout << X.size() << ' ';
    } 
    cout << endl;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
const int MOD = 998'244'353;
 
int bpow(int x, int p){
	int res = 1;
	while(p){
		if (p % 2){
			res = (res * x) % MOD;
		}
		p >>= 1;
		x = (x * x) % MOD;
	}
	return res;
}
 
int fact(int x){
	int res = 1;
	for (int i = 1; i <= x; i++){
		res = (res * i) % MOD;
	}
	return res;
}
 
void solve(){
	vector<int> c(26);
	for (int i = 0; i < 26; i++){
		cin >> c[i];
	}
 
	int s = accumulate(c.begin(), c.end(), 0ll);
	
	vector<int> dp(s + 1);
	dp[0] = 1;
 
	for (int i = 0; i < 26; i++){
		if (c[i] == 0){
			continue;
		}
		for (int j = s; j >= 0; j--){
			if (j + c[i] <= s){
				dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % MOD;
			}
		}
	}
 
	int ans = dp[s / 2] * fact(s / 2) % MOD * fact((s + 1) / 2) % MOD;
	for (int i = 0; i < 26; i++){
		ans = (ans * bpow(fact(c[i]), MOD - 2)) % MOD;
	}
 
	cout << ans << '\n';
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

#include<bits/stdc++.h>
using namespace std;
 
long long dp[40][120][2][2];
 
void count(vector<int>& num){
	int m = num.size();
	memset(dp, 0, sizeof(dp));
 
	dp[0][0][1][0] = 1;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < 3 * m + 2; j++){
			for (int k = 0; k < 4; k++){
				if (j + k >= 3 * m + 2){
					break;
				}
				if (num[i] == k){
					dp[i + 1][j + k][1][0] += dp[i][j][1][0];
					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
					if (k == 0){
						dp[i + 1][j + k][1][1] += dp[i][j][1][1];
						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
					}
				}
				else if (num[i] > k){
					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
					dp[i + 1][j + k][0][0] += dp[i][j][1][0];
					if (k == 0){
						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
						dp[i + 1][j + k][0][1] += dp[i][j][1][1];
					}
				}
				else{
					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
					if (k == 0){
						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
					}
				}
			}
			if (j + 4 < 3 * m + 2){
				if (num[i] == 4){
					dp[i + 1][j + 4][1][1] += dp[i][j][1][0];
					dp[i + 1][j + 4][0][1] += dp[i][j][0][0];				
				}
				else{
					dp[i + 1][j + 4][0][1] += dp[i][j][0][0];					
				}
			}
		}
	}
}
 
void solve(){
	long long l, r, k;
	cin >> l >> r >> k;
	l--;
	if (k >= 90){
		cout << 0 << '\n';
		return;
	}
 
	vector<long long> zeb;
	long long cur = 0;
	for (int i = 0; i < 60; i += 2){
		cur ^= (1ll << i);
		zeb.emplace_back(cur);
	}
	int m = zeb.size();
 
	vector<int> num_l;
	for (int i = m - 1; i >= 0; i--){
		int cnt = 0;
		while(l >= zeb[i]){
			cnt++;
			l -= zeb[i];
		}
		num_l.emplace_back(cnt);
	}
 
	vector<int> num_r;
	for (int i = m - 1; i >= 0; i--){
		int cnt = 0;
		while(r >= zeb[i]){
			cnt++;
			r -= zeb[i];
		}
		num_r.emplace_back(cnt);
	}
 
	count(num_r);
	long long ans = dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
	count(num_l);
	ans -= dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
	cout << ans << '\n';
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	while(t--){
	    solve();
	}
}

#include <bits/stdc++.h>
using namespace std;
 
vector<long long> z;
 
void precalc()
{
    z = {1ll};
    while(z.back() < 1e18)
        z.push_back(4 * z.back() + 1);
}
 
map<pair<long long, long long>, long long> dp;
 
long long get(long long r, long long x)
{
    if(dp.count(make_pair(r, x))) return dp[make_pair(r, x)];
    long long& d = dp[make_pair(r, x)];
    if(x > 4 * z.size()) return d = 0;
    if(x < 0) return d = 0;
    if(r == 0) return d = 0;
    if(r == 1)
    {
        if(x == 0) return d = 1;
        return d = 0;
    }
    auto it = lower_bound(z.begin(), z.end(), r);
    --it;
    long long y = *it;
    return d = get(y, x) + get(r - y, x - 1);
}
 
int main() 
{
    precalc();
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        long long l, r, x;
        cin >> l >> r >> x;
        cout << get(r + 1, x) - get(l, x) << endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
bool is_palindrom(const string& s){
    int n = s.size();
    for (int i = 0; i < n / 2; i++){
        if (s[i] != s[n - i - 1]){
            return false;
        }
    }
    return true;
}
 
bool check_pattern(const string& s){
    int n = s.size();
    char a = 'a', b = 'b';
    int cnt_a = 0, cnt_b = 0;
    for (int i = 0; i < n; i++){
        if (s[i] == a){
            cnt_a++;
        }
        else{
            cnt_b++;
        }
    }
    if (cnt_a % 2 == 1){
        swap(cnt_a, cnt_b);
        swap(a, b);
    }
    if (s[n / 2] != b){
        return false;
    }
    if (!is_palindrom(s)){
        return false;
    }
 
    cnt_b--;
    cnt_a /= 2;
    cnt_b /= 2;
 
    if (cnt_a > cnt_b){
        swap(cnt_a, cnt_b);
        swap(a, b);
    }
 
    if (s[0] == a){
        cnt_a--;
    }
    else{
        cnt_b--;
    }
 
    for (int i = 1; i < n / 2; i++){
        if (s[i] == s[i - 1]){
            if (cnt_a == 0){
                return true;
            }
            return false;
        }
        if (s[i] == a){
            cnt_a--;
        }
        else{
            cnt_b--;
        }
    }
 
    return true;
}
 
pair<int, int> find_valid_move_odd(string s){
    int n = s.size();
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            swap(s[i], s[j]);
            if (check_pattern(s)){
                return {i, j};
            }
            swap(s[i], s[j]);
        }
    }
    return {-1, -1};
}
 
pair<int, int> find_valid_move_even(string s){
    int n = s.size();
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j <= i; j++){
            if (s[i] == s[j] && i != j){
                continue;
            }
            if (i == j && i != n - 1){
                continue;
            }
            swap(s[i], s[j]);
            int cnt = 0;
            s += 'a';
            for (int k = n; k >= 0; k--){
                for (int l = 0; l <= k; l++){
                    if (s[k] == s[l] && k != l){
                        continue;
                    }
                    if (k == l && k != n){
                        continue;
                    }                
                    swap(s[k], s[l]);
                    if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
                        cnt++;
                        swap(s[k], s[l]);
                        break;
                    }
                    swap(s[k], s[l]);
                }
                if (cnt == 1){
                    break;
                }
            }
            s.pop_back();
            if (cnt == 1){
                s += 'b';
                for (int k = n; k >= 0; k--){
                    for (int l = 0; l <= k; l++){
                        if (s[k] == s[l] && k != l){
                            continue;
                        }
                        if (k == l && k != n){
                            continue;
                        }   
                        swap(s[k], s[l]);
                        if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
                            return {i, j};
                        }
                        swap(s[k], s[l]);
                    }
                }
                s.pop_back();
            }
            swap(s[i], s[j]);
        }
    }
    return {-1, -1};
}
 
void solve(){
    string t = "";
    while(1){
        char ch;
        cin >> ch;
        if (ch == '0'){
            break;
        }
 
        t += ch;
 
        if (t.size() % 2 == 1){
            auto [l, r] = find_valid_move_odd(t);
            swap(t[l], t[r]);
            cout << l + 1 << ' ' << r + 1 << endl;
        }
        else{
            auto [l, r] = find_valid_move_even(t);
            swap(t[l], t[r]);
            cout << l + 1 << ' ' << r + 1 << endl;
        }
    }
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

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

#define forn(i, n) for(int i = 0; i < int(n); i++) 
const int N = 100;
 
bool dp[N][N];
pair<int, int> nxt[N][N][2];
bitset<N> cur;
bitset<N> form[N][N];
 
int main(){
	forn(i, N) forn(j, N) dp[i][j] = (i + j) % 2;
	for (int len = 1; len < N; len += 2){
		forn(x, len + 1){
			int y = len - x;
			int nx = x, ny = y;
			int i = 0;
			while (nx > 1 || ny > 1){
				if (nx > 1){
					nx -= 2;
					++i;
				}
				if (ny > 1){
					form[x][y][i] = form[x][y][len - i - 1] = 1;
					ny -= 2;
					++i;
				}
			}
			if (ny > 0){
				form[x][y][i] = 1;
			}
		}
	}
	for (int len = N - 3; len >= 1; len -= 2){
		forn(x, len + 1){
			int y = len - x;
			cur = form[x][y];
			forn(c, 2){
				cur[len] = c;
				bool found = false;
				forn(l, len + 1){
					forn(r, l + 1){
						if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
						bool ok = true;
						forn(d, 2){
							cur[len + 1] = d;
							int nx = x + (c == 0) + (d == 0);
							int ny = y + (c == 1) + (d == 1);
							if ((cur ^ form[nx][ny]).count() > 2){
								ok = false;
								break;
							}
						}
						if (ok){
							found = true;
							nxt[x][y][c] = {l, r};
						}
						if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
						if (found) break;
					}
					if (found) break;
				}
				if (!found){
					dp[x][y] = false;
					break;
				}
			}
		}
	}
	string s;
	cur.reset();
	for (int i = 0;; ++i){
		cin >> s;
		if (s == "0") break;
		int c = s[0] - 'a';
		int py = cur.count(), px = i - py;
		cur[i] = c;
		int nx = px + (c == 0), ny = py + (c == 1);
		int l = -1, r = -1;
		if (i % 2 == 1){
			auto res = nxt[px][py][c];
			if (res.first != res.second){
				l = res.first;
				r = res.second;
			}
		}
		else{
			assert(dp[nx][ny]);
			bitset<N> dif = cur ^ form[nx][ny];
			assert(dif.count() <= 2);
			if (dif.count() == 2){
				l = dif._Find_first();
				r = dif._Find_next(l);
			}
		}
		if (l == -1){
			cout << 0 << " " << 0 << endl;
		}
		else{
			cout << l + 1 << " " << r + 1 << endl;
			if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
		}
	}
}

t = int(input())
for T in range(t):
	la, lb = map(int, input().split())
	ra, rb = map(int, input().split())
	if la > lb:
		la, lb, ra, rb = lb, la, rb, ra
	if la < lb and rb < ra:
		print("NO")
	else:
		print("YES")

#include <bits/stdc++.h>
 
using namespace std;
 
void solve(){
	long long x, y, k;
	cin >> x >> y >> k;
	while (k > 0 && x != 1) {
		long long ost = (x / y + 1) * y - x;
                ost = max(1ll, ost);
                ost = min(ost, k);
                x += ost;
		while (x % y == 0) {
			x /= y;
		}
		k -= ost;
	}
	cout << x + k % (y - 1) << '\n';
}
 
int 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;
}

All the numbers $$$a_{i}$$$ are positive, can it help somehow?

Try using dynamic programming.

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1000000007;
 
void solve(){
	int n, l, r;
	cin >> n >> l >> r;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
 
	vector<long long> pref(n + 1);
	for (int i = 0; i < n; i++){
		pref[i + 1] = pref[i] + a[i];
	}
 
	vector<int> dp(n + 1);
	int s = 0;
	int j = -1;
	for (int i = 0; i < n; i++){
		dp[i + 1] = max(dp[i + 1], dp[i]);
		if (j < i){
			j = i;
			s = 0;
		}
		while(j < n && s < l){
			s += a[j++];
		}
		if (s >= l && s <= r){
			dp[j] = max(dp[j], dp[i] + 1);
		}
		s -= a[i];
	}
 
	cout << dp[n] << '\n';
}
 
int 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;
}

t = int(input())
for T in range(t):
	n, l, r = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	cur = 0
	L, R = 0, 0
	while L < n:
		while R < n and cur < l:
			cur += a[R]
			R += 1
		if l <= cur and cur <= r:
			ans += 1
			L = R
			cur = 0
		else:
			cur -= a[L]
			L += 1
	print(ans)

How does the difference between heights change if we choose a specific submatrix?

It is worth reducing the problem to a mathematical construction. Maybe something from number theory can help?

import math
 
def solve():
    n, m, k = map(int, input().split())
    a = [[int(x) for x in input().split()] for j in range(n)]
    s = [input() for i in range(n)]
    pref = [[0 for i in range(m + 1)] for j in range(n + 1)]
    diff = 0
    for i in range(n):
        cur = 0
        for j in range(m):
            if s[i][j] == '1':
                cur += 1
                diff += a[i][j]
            else:
                diff -= a[i][j]
            pref[i + 1][j + 1] = pref[i][j + 1] + cur
    if diff == 0:
        print("YES")
        return
    g = 0
    for i in range(n - k + 1):
        for j in range(m - k + 1):
            f = pref[i + k][j + k] - pref[i + k][j] - pref[i][j + k] + pref[i][j]
            f = abs(k * k - 2 * f)
            g = math.gcd(g, f)
    if g == 0 or diff % g != 0:
        print("NO")
    else:
        print("YES")
 
 
if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

Try using the divide-and-conquer approach.

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 1000000007;
 
map<pair<long long, int>, tuple<int, long long, long long>> mem;
 
tuple<int, long long, long long> calc(long long n, int k){
	if (k < 0){
		return tuple{0, 0ll, 0ll};
	}
	if (n == 1){
		return tuple{1, 1ll, 1ll};
	}
	int bit = 63 - __builtin_clzll(n);
	long long mid = (1ll << bit);
	if (mid == n){
		mid >>= 1;
		if (mem.count({n, k})){
			return mem[{n, k}];
		}
	}
	auto [f1, s1, e1] = calc(mid, k);
	auto [f2, s2, e2] = calc(n - mid, k - 1);
 
	int sub1 = (e1 % MOD) * ((e1 + 1) % MOD) % MOD * 500000004 % MOD;
	f1 = (f1 * 1ll - sub1 + MOD) % MOD;
	int sub2 = (s2 % MOD) * ((s2 + 1) % MOD) % MOD * 500000004 % MOD;
	f2 = (f2 * 1ll - sub2 + MOD) % MOD;
 
	long long p = (e1 + s2) % MOD;
	int f_cur = (f1 * 1ll + f2 + (p * 1ll * ((p + 1) % MOD) % MOD * 500000004 % MOD)) % MOD;
	long long s_cur = s1;
	long long e_cur = e2;
	if (s1 == e1 && s1 != 0){
		s_cur = (s1 + s2);
	}
	if (s2 == e2 && s2 != 0){
		e_cur = (e1 + e2);
	}
	if ((mid << 1) == n){
		mem[{n, k}] = tuple{f_cur, s_cur, e_cur};
	}
	return tuple{f_cur, s_cur, e_cur};
};
 
void solve(){
	long long n;
	int k;
	cin >> n >> k;
	cout << get<0>(calc(n, k)) << '\n';
}
 
int 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;
}

If you maintain a set of such indexes $$$i$$$ that $$$a_{i} \lt a_{i - 1}$$$, then can this help in any way?

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1000000007;
 
struct SegTree{
	vector<int> mn, mx;
	int n;
	SegTree(int _n): n(_n){
		mx.assign(2 * n, -inf);
		mn.resize(2 * n, inf);
	}
 
	void upd(int pos, int val){
		mx[pos + n] = val;
		mn[pos + n] = val;
		pos = (pos + n) >> 1;
		for (;pos > 0; pos >>= 1){
			mx[pos] = max(mx[pos << 1], mx[(pos << 1) | 1]);
			mn[pos] = min(mn[pos << 1], mn[(pos << 1) | 1]);
		}
	}
 
	pair<int,int> get(int l, int r){
		pair<int,int> res = {-inf, inf};
		l += n;
		r += n + 1;
		for (;l < r; l >>= 1, r >>= 1){
			if (l & 1) {
				res.first = max(res.first, mx[l]);
				res.second = min(res.second, mn[l++]);
			}
			if (r & 1) {
				res.first = max(res.first, mx[--r]);
				res.second = min(res.second, mn[r]);
			}			
		}
		return res;
	}
};
 
void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
 
	SegTree tree(n);
	set<int> st;
	for (int i = 0; i < n; i++){
		tree.upd(i, a[i]);
		if (i > 0 && a[i] < a[i - 1]){
			st.insert(i);
		}
	}
 
	function<int(int, int)> find_pref = [&](int pos, int x){
		if (pos < 0){
			return 0;
		}
		int l = 0, r = pos;
		while(l <= r){
			int m = l + (r - l) / 2;
			if (a[m] > x){
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		return r + 1;
	};
 
	function<int(int, int)> find_suff = [&](int pos, int x){
		if (pos >= n){
			return n - 1;
		}
		int l = pos, r = n - 1;
		while(l <= r){
			int m = l + (r - l) / 2;
			if (a[m] >= x){
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		return r;
	};
 
	function<void()> query = [&](){
		if (st.empty()){
			cout << -1 << ' ' << -1 << '\n';
			return;
		}
		int l = *st.begin() - 1;
		int r = *(--st.end());
 
		auto [mx, mn] = tree.get(l, r);
 
		cout << find_pref(l - 1, mn) + 1 << ' ' << find_suff(r + 1, mx) + 1 << '\n';
	};
 
	query();
	int q;
	cin >> q;
	for (int i = 0; i < q; i++){
		int pos, val;
		cin >> pos >> val;
		pos--;
		if (pos > 0 && a[pos] < a[pos - 1]){
			st.erase(pos);
		}
		if (pos + 1 < n && a[pos + 1] < a[pos]){
			st.erase(pos + 1);
		}
		a[pos] = val;
		tree.upd(pos, val);
		if (pos > 0 && a[pos] < a[pos - 1]){
			st.insert(pos);
		}
		if (pos + 1 < n && a[pos + 1] < a[pos]){
			st.insert(pos + 1);
		}
		query();
	}
}
 
int 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;
}