#include <bits/stdc++.h>
#include "random"

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &e : v) {
        cin >> e;
    }
    int maxPos = max_element(v.begin(), v.end()) - v.begin();
    int minPos = min_element(v.begin(), v.end()) - v.begin();
    cout << min({
            max(maxPos, minPos) + 1,
            (n - 1) - min(maxPos, minPos) + 1,
            (n - 1) - maxPos + minPos + 2,
            (n - 1) - minPos + maxPos + 2
    }) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  int s = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    s += a[i];
  }
  if (s % n != 0) {
    cout << "-1" << endl;
    return;
  }
  s /= n;
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (s < a[i]) {
      res++;
    }
  }
  cout << res << endl;
}

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

#include <bits/stdc++.h>
#include "random"

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<int> v(n);
    for (int &e : v) {
        cin >> e;
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += upper_bound(v.begin(), v.end(), r - v[i]) - v.begin();
        ans -= lower_bound(v.begin(), v.end(), l - v[i]) - v.begin();
        if (l <= 2 * v[i] && 2 * v[i] <= r) {
            ans--;
        }
    }
    cout << ans / 2 << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

const int N = 50'000;

bool isPrime[N];
vector<int> primes;

void precalc() {
  fill(isPrime + 2, isPrime + N, true);
  for (int i = 2; i * i < N; i++) {
    for (int j = i * i; j < N; j += i) {
      isPrime[j] = false;
    }
  }
  for (int i = 2; i < N; i++) {
    if (isPrime[i]) {
      primes.push_back(i);
    }
  }
}

int calcPrime(int n) {
  int res = 0;
  for (int i : primes) {
    if (i * i > n) {
      break;
    }
    while (n % i == 0) {
      n /= i;
      res++;
    }
  }
  if (n > 1) {
    res++;
  }
  return res;
}

map<int, int> decompose(int n) {
  map<int, int> a;
  for (int i : primes) {
    if (i * i > n) {
      break;
    }
    int p = 0;
    while (n % i == 0) {
      n /= i;
      p++;
    }
    if (p > 0) {
      a[i] = p;
    }
  }
  if (n > 1) {
    a[n] = 1;
  }
  return a;
}

bool check(const map<int, int> &divs,
           map<int, int>::const_iterator it,
           map<int, int> &divsA,
           map<int, int> &divsB,
           int low,
           int high,
           int k) {
  if (it == divs.end()) {
    return __builtin_popcount(low) <= k && k <= high;
  }
  for (int p = 0; p <= it->second; p++) {
    int pa = divsA[it->first];
    int pb = divsB[it->first];
    int nextLow = low;
    if (p != pa) {
      nextLow |= 1;
    }
    if (p != pb) {
      nextLow |= 2;
    }
    if (check(divs, next(it), divsA, divsB, nextLow, high + pa + pb - 2 * p, k)) {
      return true;
    }
  }
  return false;
}

void solve() {
  int a, b, k;
  cin >> a >> b >> k;
  int g = __gcd(a, b);
  int low = 0;
  int high = 0;
  {
    int t;
    int ta = 1;
    while ((t = __gcd(a, g)) != 1) {
      a /= t;
      ta *= t;
    }
    high += calcPrime(a);
    if (a != 1) {
      low |= 1;
    }
    a = ta;
  }
  {
    int t;
    int tb = 1;
    while ((t = __gcd(b, g)) != 1) {
      b /= t;
      tb *= t;
    }
    high += calcPrime(b);
    if (b != 1) {
      low |= 2;
    }
    b = tb;
  }
  auto divs = decompose(g);
  auto divsA = decompose(a);
  auto divsB = decompose(b);
  cout << (check(divs, divs.begin(), divsA, divsB, low, high, k) ? "YES" : "NO") << endl;
}

int main() {
  precalc();

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

  return 0;
}

#include <bits/stdc++.h>
#include "random"

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

vector<string> split(const string& s, char p) {
    vector<string> res(1);
    for (char c : s) {
        if (c == p) {
            res.emplace_back();
        } else {
            res.back() += c;
        }
    }
    return res;
}

struct Word {
    ll len;
    ll cnt;
    string s;
};

string getFirst(string s) {
    if (s.size() < 3) {
        return s;
    }
    return s.substr(0, 3);
}

string getLast(string s) {
    if (s.size() < 3) {
        return s;
    }
    return s.substr(s.size() - 3, 3);
}

int count(const string& s, const string& p) {
    int cnt = 0;
    for (int i = 0; i + p.size() <= s.size(); i++) {
        if (s.substr(i, p.size()) == p) {
            cnt++;
        }
    }
    return cnt;
}

Word merge(const Word& a, const Word& b) {
    Word c;
    c.len = a.len + b.len;
    c.s = a.s + b.s;
    c.cnt = a.cnt + b.cnt + count(getLast(a.s) + getFirst(b.s), "haha");
    if (c.s.size() >= 7) {
        c.s = getFirst(c.s) + "@" + getLast(c.s);
    }
    return c;
}

void solve() {
    int n;
    cin >> n;
    map<string, Word> vars;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        string var;
        cin >> var;
        string opr;
        cin >> opr;
        if (opr == "=") {
            string a, plus, b;
            cin >> a >> plus >> b;
            vars[var] = merge(vars[a], vars[b]);
        } else {
            string str;
            cin >> str;
            Word word;
            word.len = str.length();
            word.cnt = count(str, "haha");
            word.s = str;
            vars[var] = word;
        }
        ans = vars[var].cnt;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <iostream>

using namespace std;

void solve () {
  int L, R;
  cin >> L >> R;

  int ans = 0;
  while (L != 0 || R != 0) {
    ans += R - L;
    L /= 10;
    R /= 10;
  }
  cout << ans << '\n';
}

int main () {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int testc;
  cin >> testc;

  for (int i = 0; i < testc; i++) {
    solve();
  }
}

#include <bits/stdc++.h>
#include "random"

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

void solve() {
    ll x, y, a, b;
    cin >> x >> y >> a >> b;
    ll l = 0, r = 1e9 + 100;
    if (a == b) {
        cout << min(x, y) / a << "\n";
        return;
    }
    if (a < b) {
        swap(a, b);
    }
    while (r - l > 1) {
        ll m = (l + r) / 2;
        ll right = floorl((x - m * b) * 1.0l / (a - b));
        ll left = ceill((y - m * a) * 1.0l / (b - a));
        if (max(left, 0ll) <= min(right, m)) {
            l = m;
        } else {
            r = m;
        }
    }
    cout << l << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (char c = 'A'; c <= 'Z'; c++) {
        int first = n;
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                first = min(first, i);
                last = max(last, i);
            }
        }
        for (int i = first; i <= last; i++) {
            if (s[i] != c) {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

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

using ll = long long;

void solve() {
  int n;
  cin >> n;
  int res = 0;
  for (ll pw = 1; pw <= n; pw = pw * 10 + 1) {
    for (int d = 1; d <= 9;  d++) {
      if (pw * d <= n) {
        res++;
      }
    }
  }
  cout << res << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

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

void solve() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << "1" << endl;
    return;
  } else if (n == 2) {
    cout << "-1" << endl;
    return;
  }
  vector<vector<int>> a(n, vector<int>(n));
  a[0][0] = 1;
  a[n - 1][n - 1] = n * n;
  int x = n * n - 1;
  for (int i = 1; i + 1 < n; i++) {
    for (int j = i; j >= 0; j--, x--) {
      a[i - j][j] = x;
    }
  }
  x = 2;
  for (int j = n - 2; j > 0; j--) {
    for (int i = 0; i < n - j; i++, x++) {
      a[n - i - 1][j + i] = x;
    }
  }
  for (int i = n - 1; i >= 0; i--, x++) {
    a[i][n - i - 1] = x;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

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

void solve() {
  int n;
  cin >> n;
  map<int, int> a;
  long long res = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x -= i;
    res += a[x];
    a[x]++;
  }
  cout << res << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt = 0;
	for(auto x : s)
		cnt += (x == '*' ? 1 : 0);
	int pos = -1;
	int cur = -1;
	for(int i = 0; i < n; i++)
	{
	 	if(s[i] == '*')
	 	{
	 	    cur++;
	 	    if(cur == cnt / 2)
	 	    	pos = i;
	 	}	
	}
	long long ans = 0;
	cur = pos - cnt / 2;
	for(int i = 0; i < n; i++)
		if(s[i] == '*')
		{
		 	ans += abs(cur - i);
		 	cur++;
		}
	cout << ans << endl;
}
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	cin >> tc;
	for(int i = 0; i < tc; i++)
	{
	 	solve();
	}
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

void calc(int l, int r, int k) {
    if (l == r) {
        cout << "! " << l << endl;
        return;
    }
    int m = (l + r) / 2;
    cout << "? " << l << " " << m << endl;
    int sum;
    cin >> sum;
    if ((m - l + 1) - sum >= k) {
        calc(l, m, k);
    } else {
        calc(m + 1, r, k - (m - l + 1) + sum);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t, k;
    cin >> n >> t >> k;
    calc(1, n, k);
}

#include <bits/stdc++.h>

using namespace std;

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

map<pair<int,int>, int> cache;

void dec(int pos, int L, int R) {
    cache[{L, R}]--;

    if (L != R) {
        int M = (L + R) / 2;
        if (pos <= M)
            dec(pos, L, M);
        else
            dec(pos, M + 1, R);
    }
}

int main() {
    int n, cases;
    cin >> n >> cases;
    forn(case_, cases) {
        int k;
        cin >> k;
        int L = 0, R = n - 1;
        while (L != R) {
            int M = (L + R) / 2;
            
            pair<int,int> range = make_pair(L, M);
            if (cache.count(range) == 0) {
                cout << "? " << range.first + 1 << " " << range.second + 1 << endl;
                cin >> cache[range];
                cache[range] = range.second - range.first + 1 - cache[range];
            }

            int value = cache[range];
            if (k <= value)
                R = M;
            else {
                k -= value;
                L = M + 1;
            }
        }

        cout << "! " << L + 1 << endl;
        dec(L, 0, n - 1);
    }
}

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

const int MAX_N = 2010;

int dd[4][2] = {
        {1, 0},
        {0, 1},
        {-1, 0},
        {0, -1}
};

void bfs(int sx, int sy, vector<vector<int>> &d, vector<vector<int>> &a) {
    int n = d.size();
    int m = d[0].size();
    queue<pair<int, int>> q;
    q.push({sx, sy});
    d[sx][sy] = 1;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto [dx, dy] : dd) {
            int tx = x + dx;
            int ty = y + dy;
            if (tx >= 0 && ty >= 0 && tx < n && ty < m && d[tx][ty] == 0 && a[tx][ty] != -1) {
                d[tx][ty] = d[x][y] + 1;
                q.push({tx, ty});
            }
        }
    }
    for (auto &e : d) {
        for (auto &i : e) {
            i--;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, w;
    cin >> n >> m >> w;
    vector<vector<int>> a(n, vector<int>(m));
    vector<vector<int>> d1(n, vector<int>(m));
    vector<vector<int>> d2(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    bfs(0, 0, d1, a);
    bfs(n - 1, m - 1, d2, a);
    ll bestFinish = 1e18;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (d2[i][j] != -1 && a[i][j] >= 1) {
                bestFinish = min(bestFinish, a[i][j] + w * 1ll * d2[i][j]);
            }
        }
    }
    ll ans = w * 1ll * d1[n - 1][m - 1];
    if (d1[n - 1][m - 1] == -1) {
        ans = 1e18;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (d1[i][j] != -1 && a[i][j] >= 1 && bestFinish != 1e18) {
                ans = min(ans, w * 1ll * d1[i][j] + a[i][j] + bestFinish);
            }
        }
    }
    if (ans == 1e18) {
        cout << -1;
    } else {
        cout << ans;
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &e : v) {
        cin >> e;
    }
    vector<int> a = v;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if (v[i] != a[1]) {
            cout << i + 1 << "\n";
        }
    }
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {    
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<string> f(n);
        vector<pair<int,int>> p;
        forn(i, n) {
            cin >> f[i];
            forn(j, n)
                if (f[i][j] == '*')
                    p.push_back({i, j});
        }

        p.push_back(p[0]);
        p.push_back(p[1]);
        if (p[0].first == p[1].first) {
            p[2].first = (p[2].first + 1) % n;
            p[3].first = (p[3].first + 1) % n;
        } else if (p[0].second == p[1].second) {
            p[2].second = (p[2].second + 1) % n;
            p[3].second = (p[3].second + 1) % n;
        } else
            swap(p[2].first, p[3].first);

        f[p[2].first][p[2].second] = '*';
        f[p[3].first][p[3].second] = '*';
        forn(i, n)
            cout << f[i] << endl;
    }
}

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

void no() {
  cout << "-1" << endl;
}

void solve() {
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  for (int times = 0; times < 2; times++) {
    for (int i = 0; i < (int) s.size(); i++) {
      int j = (int) s.size() - i - 1;
      if (s[i] != '?') {
        if (s[j] == '?') {
          s[j] = s[i];
        } else if (s[i] != s[j]) {
          no();
          return;
        }
      }
    }
    reverse(s.begin(), s.end());
  }
  a -= count(s.begin(), s.end(), '0');
  b -= count(s.begin(), s.end(), '1');
  int ques = count(s.begin(), s.end(), '?');
  bool emptyMid = (s.size() % 2 == 1 && s[s.size() / 2] == '?');
  if (a < 0 || b < 0 || a + b != ques || (emptyMid && a % 2 == 0 && b % 2 == 0)) {
    no();
    return;
  }
  if (a % 2 == 1 || b % 2 == 1) {
    int i = s.size() / 2;
    if (s[i] != '?') {
      no();
      return;
    }
    s[i] = (a % 2 == 1 ? '0' : '1');
    if (a % 2 == 1) {
      a--;
    } else {
      b--;
    }
  }
  if (a % 2 == 1 || b % 2 == 1) {
    no();
    return;
  }
  for (int i = 0; i < (int) s.size(); i++) {
    if (s[i] == '?') {
      int j = s.size() - i - 1;
      if (a > 0) {
        a -= 2;
        s[i] = s[j] = '0';
      } else {
        b -= 2;
        s[i] = s[j] = '1';
      }
    }
  }
  cout << s << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

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

void no() {
  cout << "-1" << endl;
}

void solve() {
  int n;
  cin >> n;
  vector<int> b(n + 2);
  for (int &x : b) {
    cin >> x;
  }

  multiset<int> have(b.begin(), b.end());
  long long sum = accumulate(b.begin(), b.end(), 0LL);
  for (int x : b) {
    have.erase(have.find(x));
    sum -= x;
    if (sum % 2 == 0 && sum <= 2'000'000'000 && have.find(sum / 2) != have.end()) {
      have.erase(have.find(sum / 2));
      for (int y : have) {
        cout << y << " ";
      }
      cout << endl;
      return;
    }
    sum += x;
    have.insert(x);
  }
  no();
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n, l, r, s;
    cin >> n >> l >> r >> s;
    l--; r--;
    for (int first = 1; first + (r - l) <= n; first++) {
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += first + (i - l);
        }
        if (sum <= s && s - sum <= r - l + 1) {
            int needAdd = r - (s - sum) + 1;
            vector<int> ans(n);
            set<int> non_blocked;
            for (int i = 1; i <= n; i++) {
                non_blocked.insert(i);
            }
            for (int i = l; i <= r; i++) {
                ans[i] = first + (i - l);
                if (i >= needAdd) {
                    ans[i]++;
                }
                non_blocked.erase(ans[i]);
            }
            if (ans[r] > n) {
                continue;
            }
            non_blocked.erase(ans[r]);
            for (int i = 0; i < l; i++) {
                ans[i] = *non_blocked.begin();
                non_blocked.erase(non_blocked.begin());
            }
            for (int i = r + 1; i < n; i++) {
                ans[i] = *non_blocked.begin();
                non_blocked.erase(non_blocked.begin());
            }
            for (int i : ans) {
                cout << i << " ";
            }
            cout << "\n";
            return;
        }
    }
    cout << "-1\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    vector<int> b(n - 1);
    for (int &e : a) {
        cin >> e;
    }
    for (int &e : b) {
        cin >> e;
    }
    b.push_back(0);
    ll ans = 1e18;
    ll cur = 0;
    ll bal = 0;
    for (int i = 0; i < n; i++) {
        ans = min(ans, cur + max(0ll, c - bal + a[i] - 1) / a[i]);
        ll newDays = max(0ll, b[i] - bal + a[i] - 1) / a[i];
        cur += newDays + 1;
        bal += a[i] * newDays - b[i];
    }
    cout << ans << "\n";
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
    return 0;
}

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

const int N = (int) 1e7 + 100;

long long s[N];
int d[N];
int ans[N];

int main() {
  fill(d, d + N, -1);
  d[1] = 1;
  for (int i = 2; i * i < N; i++) {
    if (d[i] == -1) {
      d[i] = i;
      for (int j = i * i; j < N; j += i) {
        if (d[j] == -1) {
          d[j] = i;
        }
      }
    }
  }
  s[1] = 1;
  for (int i = 2; i < N; i++) {
    if (d[i] == -1) {
      d[i] = i;
      s[i] = i + 1;
    } else {
      int j = i;
      s[i] = 1;
      while (j % d[i] == 0) {
        j /= d[i];
        s[i] = s[i] * d[i] + 1;
      }
      s[i] *= s[j];
    }
  }
  fill(ans, ans + N, -1);
  for (int i = N - 1; i > 0; i--) {
    if (s[i] < N) {
      ans[s[i]] = i;
    }
  }
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    int c;
    cin >> c;
    cout << ans[c] << endl;
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int w, h, n;
  cin >> w >> h >> n;
  int res = 1;
  while (w % 2 == 0) {
    w /= 2;
    res *= 2;
  }
  while (h % 2 == 0) {
    h /= 2;
    res *= 2;
  }
  cout << (res >= n ? "YES\n" : "NO\n");
}

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int n;
  cin >> n;
  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < n; i++) {
    int c;
    cin >> c;
    if (c == 1) {
      cnt1++;
    } else {
      cnt2++;
    }
  }
  if ((cnt1 + 2 * cnt2) % 2 != 0) {
    cout << "NO\n";
  } else {
    int sum = (cnt1 + 2 * cnt2) / 2;
    if (sum % 2 == 0 || (sum % 2 == 1 && cnt1 != 0)) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}

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

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

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }

  vector<int> dp(n);
  for (int i = n - 1; i >= 0; i--) {
    dp[i] = a[i];
    int j = i + a[i];
    if (j < n) {
      dp[i] += dp[j];
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int &e : v) {
    cin >> e;
  }
  sort(v.rbegin(), v.rend());
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (v[i] % 2 == 0) {
        ans += v[i];
      }
    } else {
      if (v[i] % 2 == 1) {
        ans -= v[i];
      }
    }
  }
  if (ans == 0) {
    cout << "Tie\n";
  } else if (ans > 0) {
    cout << "Alice\n";
  } else {
    cout << "Bob\n";
  }
}

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

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

using pii = pair<int, int>;

struct man {
  int h, w, id;
};

bool operator<(const man &a, const man &b) {
  return tie(a.h, a.w, a.id) < tie(b.h, b.w, b.id);
}

struct my_min {
  pii mn1, mn2;
};

vector<pair<int, my_min>> createPrefMins(const vector<man>& a) {
  vector<pair<int, my_min>> prefMin;
  my_min curMin{pii(INT_MAX, -1), pii(INT_MAX, -1)};
  for (auto x : a) {
    if (x.w < curMin.mn1.first) {
      curMin.mn2 = curMin.mn1;
      curMin.mn1 = pii(x.w, x.id);
    } else {
      curMin.mn2 = min(curMin.mn2, pii(x.w, x.id));
    }
    prefMin.emplace_back(x.h, curMin);
  }
  return prefMin;
}

int findAny(const vector<pair<int, my_min>> &mins, int h, int w, int id) {
  int l = -1, r = (int) mins.size();
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (mins[m].first < h) {
      l = m;
    } else {
      r = m;
    }
  }
  if (l == -1) {
    return -1;
  }

  auto mn1 = mins[l].second.mn1;
  auto mn2 = mins[l].second.mn2;
  if (mn1.second != id) {
    return mn1.first < w ? mn1.second + 1 : -1;
  }
  return mn2.first < w ? mn2.second + 1 : -1;
}

void solve() {
  int n;
  cin >> n;
  vector<man> hor, ver;
  vector<pii> a;
  for (int i = 0; i < n; i++) {
    int h, w;
    cin >> h >> w;
    hor.push_back({h, w, i});
    ver.push_back({w, h, i});
    a.emplace_back(h, w);
  }

  sort(hor.begin(), hor.end());
  sort(ver.begin(), ver.end());

  auto horMins = createPrefMins(hor);
  auto verMins = createPrefMins(ver);

  for (int i = 0; i < n; i++) {
    auto[h, w] = a[i];
    int id = findAny(horMins, h, w, i);
    if (id == -1) {
      id = findAny(verMins, h, w, i);
    }
    cout << id << " ";
  }
  cout << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  map<int, int> v;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    v[y] |= (1 << (x - 1));
  }
  const int FULL = 3;
  v[2e9] = FULL;
  int hasLast = 0, lastColor = 0;
  for (auto[x, mask] : v) {
    if (mask != FULL && hasLast) {
      int color = (x + mask) % 2;
      if (lastColor == color) {
        cout << "NO\n";
        return;
      } else {
        hasLast = false;
      }
    } else if (mask == FULL && hasLast) {
        cout << "NO\n";
        return;
    } else if (mask != FULL) {
      lastColor = (x + mask) % 2;
      hasLast = true;
    }
  }
  cout << "YES\n";
}

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

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

vector<int> calcDist(vector<vector<int>> const &g) {
  vector<int> dist(g.size(), -1);
  dist[1] = 0;
  queue<int> pq;
  pq.push(1);
  while (!pq.empty()) {
    int u = pq.front();
    pq.pop();
    for (int v : g[u]) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        pq.push(v);
      }
    }
  }

  return dist;
}

void dfs(int u, vector<vector<int>> const &g, vector<int> const &dist, vector<int> &dp, vector<bool> &used) {
  used[u] = true;
  dp[u] = dist[u];
  for (int v : g[u]) {
    if (!used[v] && dist[u] < dist[v]) {
      dfs(v, g, dist, dp, used);
    }

    if (dist[u] < dist[v]) {
      dp[u] = min(dp[u], dp[v]);
    } else {
      dp[u] = min(dp[u], dist[v]);
    }
  }
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }

  vector<int> dist = calcDist(g);
  vector<int> dp(n + 1);
  vector<bool> used(n + 1);
  dfs(1, g, dist, dp, used);
  for (int i = 1; i <= n; i++) {
    cout << dp[i] << " ";
  }
  cout << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

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

int main() {
	int t;
	cin >> t;

	for (int test = 1; test <= t; test++) {
		string b;
		cin >> b;

		string a = b.substr(0, 2);

		for (int i = 3; i < b.size(); i += 2) {
			a += b[i];
		}

		cout << a << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;
using ld = long double;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    int a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x % 2 != i % 2) {
            if (i % 2 == 0) {
                a++;
            } else {
                b++;
            }
        }
    }
    if (a != b) {
        cout << -1 << endl;
    } else {
        cout << a << endl;
    }
}

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

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

int main() {
	int t;
	cin >> t;

	for (int test = 1; test <= t; test++) {
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;

		int res = 0;

		for (int i = 0; i < n;) {
			int j = i + 1;

			for (; j < n && s[j] != '1'; j++);

			int left = s[i] == '1' ? k : 0;
			int right = j < n && s[j] == '1' ? k : 0;
			int len = j - i;

			if (left == k) {
				len--;
			}

			len -= left + right;

			if (len > 0) {
				res += (len + k) / (k + 1);
			}

			i = j;
		}

		cout << res << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int q;
    cin >> q;
    forn(qq, q) {
        string s;
        cin >> s;
        int n;
        cin >> n;
        vector<int> b(n);
        forn(i, n)
            cin >> b[i];
        vector<vector<int>> groups;
        while (true) {
            vector<int> pos;
            forn(i, n)
                if (b[i] == 0)
                    pos.push_back(i);
            if (pos.empty())
                break;
            groups.push_back(pos);
            forn(i, n)
                if (b[i] == 0)
                    b[i] = INT_MAX;
                else
                    for (int pp: pos)
                        b[i] -= abs(i - pp);
        }
        map<char, int> cnts;
        forn(i, s.size())
            cnts[s[i]]++;
        auto j = cnts.rbegin();
        string t(n, '?');
        for (auto g: groups) {
            while (j->second < g.size())
                j++;
            for (int pp: g)
                t[pp] = j->first;
            j++;
        }
        cout << t << endl;
    }
}

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

int main() {
	int test;
	cin >> test;

	while (test--) {
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;

		vector<int> cnt(26);

		for (char c : s) {
			cnt[c - 'a']++;
		}

		for (int len = n; len >= 1; len--) {
			vector<bool> used(len);
			vector<int> cycles;

			for (int i = 0; i < len; i++) {
				if (used[i]) {
					continue;
				}

				int j = (i + k) % len;
				used[i] = true;
				cycles.push_back(0);
				cycles.back()++;

				while (!used[j]) {
					cycles.back()++;
					used[j] = true;
					j = (j + k) % len;
				}
			}

			vector<int> cur_cnt(cnt);

			sort(cycles.begin(), cycles.end());
			sort(cur_cnt.begin(), cur_cnt.end());

			bool can_fill = true;

			while (!cycles.empty()) {
				if (cur_cnt.back() < cycles.back()) {
					can_fill = false;
					break;
				} else {
					cur_cnt.back() -= cycles.back();
					cycles.pop_back();
					sort(cur_cnt.begin(), cur_cnt.end());
				}
			}

			if (can_fill) {
				cout << len << endl;
				break;
			}
		}
	}
}

#include <bits/stdc++.h>

using namespace std;
using ld = long double;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        a[i] = {v[i], i};
    }
    sort(a.begin(), a.end());
    vector<int> p(n);
    int j = 0;
    unordered_multiset<int> next;
    for (int i = 0; i < n; i++) {
        if (i > 0 && a[i].first != a[i - 1].first) {
            j++;
        }
        p[a[i].second] = j;
        next.insert(j);
    }
    unordered_map<int, int> d;
    vector<int> dp1(n), dp2(n), dp3(n), cnt(n);
    for (int i = 0; i < n; i++) {
        if (next.count(p[i])) {
            next.erase(next.find(p[i]));
        }
        if (d.count(p[i] - 1)) {
            if (!d.count(p[i])) {
                dp2[i] = max(dp2[i], dp1[d[p[i] - 1]] + 1);
                if (!next.count(p[i] - 1)) {
                    dp2[i] = max(dp2[i], dp2[d[p[i] - 1]] + 1);
                }
            }
            if (!next.count(p[i] - 1)) {
                dp3[i] = max(dp3[i], dp2[d[p[i] - 1]] + 1);
            }
            dp3[i] = max(dp3[i], dp1[d[p[i] - 1]] + 1);
        }
        if (d.count(p[i])) {
            dp3[i] = max(dp3[i], dp3[d[p[i]]] + 1);
            dp2[i] = max(dp2[i], dp2[d[p[i]]] + 1);
            dp1[i] = dp1[d[p[i]]] + 1;
        } else {
            dp1[i] = 1;
        }
        dp2[i] = max(dp2[i], dp1[i]);
        dp3[i] = max(dp3[i], dp2[i]);
        d[p[i]] = i;
    }
    cout << n - *max_element(dp3.begin(), dp3.end()) << "\n";
}

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