#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    ll n, m, x;
    cin >> n >> m >> x;
    x--;
    ll col = x / n;
    ll row = x % n;
    cout << row * m + col + 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;

void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int res = 1;
  int i = s.find_first_of('*');
  while (true) {
    int j = min(n - 1, i + k);
    for (; i < j && s[j] == '.'; j--) {}
    if (i == j) {
      break;
    }
    res++;
    i = j;
  }
  cout << res << "\n";
}

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() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    int ans = 0;
    for (int len = 1; len <= min(n, m); len++) {
        for (int i = 0; i + len <= n; i++) {
            for (int j = 0; j + len <= m; j++) {
                if (a.substr(i, len) == b.substr(j, len)) {
                    ans = max(ans, len);
                }
            }
        }
    }
    cout << a.size() + b.size() - 2 * ans << "\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;
using ll = long long;

void solve() {
    priority_queue<pair<int, int>> q;
    int n;
    cin >> n;
    map<int, int> v;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[x]++;
    }
    for (auto [x, y] : v) {
        q.push({y, x});
    }
    int sz = n;
    while (q.size() >= 2) {
        auto [cnt1, x1] = q.top();
        q.pop();
        auto [cnt2, x2] = q.top();
        q.pop();
        cnt1--;
        cnt2--;
        sz -= 2;
        if (cnt1) {
            q.push({cnt1, x1});
        }
        if (cnt2) {
            q.push({cnt2, x2});
        }
    }
    cout << sz << "\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;

void placeLeft(vector<int> &q, bool minimize) {
  set<int> left;
  for (int i = 1; i <= (int) q.size(); i++) {
    left.insert(i);
  }
  for (int i : q) {
    if (i != -1) {
      left.erase(i);
    }
  }
  int lastPlaced = -1;
  for (int &i : q) {
    if (i == -1) {
      set<int>::const_iterator it;
      if (minimize) {
        it = left.begin();
      } else {
        it = --left.lower_bound(lastPlaced);
      }
      i = *it;
      left.erase(it);
    } else {
      lastPlaced = i;
    }
  }
}

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

  vector<int> res1(n, -1), res2(n, -1);
  for (int i = 0, lastPlaced = -1; i < n; lastPlaced = q[i], i++) {
    if (lastPlaced != q[i]) {
      res1[i] = q[i];
      res2[i] = q[i];
    }
  }
  placeLeft(res1, true);
  placeLeft(res2, false);
  for (int x : res1) {
    cout << x << " ";
  }
  cout << "\n";
  for (int x : res2) {
    cout << x << " ";
  }
  cout << "\n";
}

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

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

bool isLeftArrow(int r, int c) {
  return (r + c) % 2 == 0;
}

bool isRightArrow(int r, int c) {
  return (r + c) % 2 == 1;
}

int calcDist(int r1, int c1, int r2, int c2) {
  if (r1 - c1 == r2 - c2) {
    return isRightArrow(r1, c1) ? 0 : r2 - r1;
  }
  r2 -= r1 - 1;
  c2 -= c1 - 1;
  if (isLeftArrow(r1, c1)) {
    return (r2 - c2) / 2;
  } else {
    return (r2 - c2 + 1) / 2;
  }
}

void solve() {
  int n;
  cin >> n;
  vector<int> r(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> r[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  vector<pair<int, int>> pts;
  for (int i = 0; i < n; i++) {
    pts.emplace_back(r[i], c[i]);
  }
  sort(pts.begin(), pts.end());
  int curR = 1, curC = 1;
  int res = 0;
  for (auto[nextR, nextC] : pts) {
    res += calcDist(curR, curC, nextR, nextC);
    curR = nextR;
    curC = nextC;
  }
  cout << res << "\n";
}

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

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

int distinct(string s) {
  sort(s.begin(), s.end());
  return unique(s.begin(), s.end()) - s.begin();
}

string filter(const string &s, char c) {
  string t;
  bool foundFirst = false;
  for (char a : s) {
    if (a != c && foundFirst) {
      t += a;
    } else if (a == c) {
      foundFirst = true;
    }
  }
  return t;
}

void solve() {
  string s;
  cin >> s;
  int m = distinct(s);
  unordered_set<char> used(s.begin(), s.end());
  string t;
  while (m > 0) {
    char maxC = -1;
    for (char c : used) {
      if (distinct(filter(s, c)) == m - 1) {
        maxC = max(maxC, c);
      }
    }
    t += maxC;
    s = filter(s, maxC);
    used.erase(maxC);
    m--;
  }
  cout << t << "\n";
}

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;
  int last;
  cin >> last;
  int ans = 0;
  for (int i = 1; i < n; i++) {
    int nw;
    cin >> nw;
    int a = min(last, nw), b = max(last, nw);
    while (a * 2 < b) {
      ans++;
      a *= 2;
    }
    last = nw;
  }
  cout << ans << "\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;
  }

  int res = 0;
  vector<int> cnt(3);
  for (int x = 0; x <= 2; x++) {
      for (int i = 0; i < n; i++) {
          if (a[i] % 3 == x) {
              cnt[x]++;
          }
      }
  }
  
  while (*min_element(cnt.begin(), cnt.end()) != n / 3) {
      for (int i = 0; i < 3; i++) {
          if (cnt[i] > n / 3) {
              res++;
              cnt[i]--;
              cnt[(i + 1) % 3]++;
          }
      }
  }
  cout << res << endl;
}

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

#include <bits/stdc++.h>

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

const ll N = 1'000'000'000'000L;

unordered_set<ll> cubes;

void precalc() {
  for (ll i = 1; i * i * i <= N; i++) {
    cubes.insert(i * i * i);
  }
}

void solve() {
  ll x;
  cin >> x;
  for (ll i = 1; i * i * i <= x; i++) {
    if (cubes.count(x - i * i * i)) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

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

#include <bits/stdc++.h>

using namespace std;

void build(int l, int r, vector<int> const &a, vector<int> &d, int curD = 0) {
  if (r < l) {
    return;
  }
  if (l == r) {
    d[l] = curD;
    return;
  }
  int m = l;
  for (int i = l + 1; i <= r; i++) {
    if (a[m] < a[i]) {
      m = i;
    }
  }
  d[m] = curD;
  build(l, m - 1, a, d, curD + 1);
  build(m + 1, r, a, d, curD + 1);
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  vector<int> d(n);
  build(0, n - 1, a, d);
  for (int x :d) {
    cout << x << " ";
  }
  cout << endl;
}

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

def win(pos : int, a : list):
    power = a[pos]
    for i in range(len(a)):
        if i == pos:
            continue
        if power < a[i]:
            return False
        power += a[i]
    return True

t = int(input())

while t > 0:
    t -= 1
    n = int(input())
    a = list(map(int, input().split(' ')))
    b = a.copy()
    a.sort()

    l = -1
    r = n - 1
    while r - l > 1:
        m = (l + r) // 2
        if (win(m, a)):
            r = m
        else:
            l = m

    winIds = []
    for i in range(n):
        if b[i] >= a[r]:
            winIds.append(i + 1)

    print(len(winIds))
    print(*winIds)

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

void solve() {
  int n;
  cin >> n;
  map<int, int> cnt;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  map<int, int> groupedByCnt;
  for (auto[x, y] : cnt) {
    groupedByCnt[y]++;
  }

  int res = n;
  int left = 0, right = n, rightCnt = (int) cnt.size();
  for (auto[x, y] : groupedByCnt) {
    res = min(res, left + right - rightCnt * x);
    left += x * y;
    right -= x * y;
    rightCnt -= y;
  }
  cout << res << 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;
  vector<ll> a(n);
  ll allSum = 0;
  vector<ll> pref;
  vector<int> ind;
  int curInd = 0;
  for (ll &e : a) {
    cin >> e;
    allSum += e;
    if (pref.empty() || allSum > pref.back()) {
      pref.push_back(allSum);
      ind.push_back(curInd);
    }
    curInd++;
  }
  for (int q = 0; q < m; q++) {
    ll x;
    cin >> x;
    if (pref.back() < x && allSum <= 0) {
      cout << -1 << " ";
      continue;
    }
    ll needTimes = 0;
    if (pref.back() < x) {
      needTimes = (x - pref.back() + allSum - 1) / allSum;
    }
    x -= needTimes * allSum;
    cout << needTimes * n + ind[lower_bound(pref.begin(), pref.end(), x) - pref.begin()] << " ";
  }
  cout << "\n";
}

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

#include <bits/stdc++.h>

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

void solve() {
  ll n;
  cin >> n;
  if (n & (n - 1)) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}

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

#include <bits/stdc++.h>

#include <utility>
using namespace std;

using pii = pair<int, int>;

int main() {
  int test;
  cin >> test;
  while (test-- > 0) {
    int n;
    cin >> n;
    int cnt2021 = n % 2020;
    int cnt2020 = (n - cnt2021) / 2020 - cnt2021;
    if (cnt2020 >= 0 && 2020 * cnt2020 + 2021 * cnt2021 == n) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
  return 0;
}

#include <bits/stdc++.h>

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

void solve() {
  int A, B, k;
  cin >> A >> B >> k;
  vector<int> a(A), b(B);
  vector<pair<int, int>> edges(k);
  for (auto &[x, y] : edges) {
    cin >> x;
  }
  for (auto &[x, y] : edges) {
    cin >> y;
  }
  for (auto &[x, y] : edges) {
    x--;
    y--;
    a[x]++;
    b[y]++;
  }
  ll ans = 0;
  for (auto &[x, y] : edges) {
    ans += k - a[x] - b[y] + 1;
  }
  cout << ans / 2 << "\n";
}

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

#include <bits/stdc++.h>

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

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a, b;
  vector<int> v(n);
  for (int &e : v) {
    cin >> e;
  }
  for (int &e : v) {
    int x;
    cin >> x;
    if (x == 1) {
      a.push_back(e);
    } else {
      b.push_back(e);
    }
  }
  sort(a.rbegin(), a.rend());
  sort(b.rbegin(), b.rend());
  ll curSumA = 0;
  int r = (int)b.size();
  ll curSumB = accumulate(b.begin(), b.end(), 0ll);
  int ans = INT_MAX;
  for (int l = 0; l <= a.size(); l++) {
    while (r > 0 && curSumA + curSumB - b[r - 1] >= m) {
      r--;
      curSumB -= b[r];
    }
    if (curSumB + curSumA >= m) {
      ans = min(ans, 2 * r + l);
    }
    if (l != a.size()) {
      curSumA += a[l];
    }
  }
  cout << (ans == INT_MAX ? -1 : ans) << "\n";
}

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

#include <bits/stdc++.h>

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

int mod = 1e9 + 7;

int fast_pow(int a, int p) {
  int res = 1;
  while (p) {
    if (p % 2 == 0) {
      a = a * 1ll * a % mod;
      p /= 2;
    } else {
      res = res * 1ll * a % mod;
      p--;
    }
  }
  return res;
}

int fact(int n) {
  int res = 1;
  for (int i = 1; i <= n; i++) {
    res = res * 1ll * i % mod;
  }
  return res;
}

int C(int n, int k) {
  return fact(n) * 1ll * fast_pow(fact(k), mod - 2) % mod * 1ll * fast_pow(fact(n - k), mod - 2) % mod;
}

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> cnt(n + 1);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  for (int i = n; i >= 0; i--) {
    if (cnt[i] >= k) {
      cout << C(cnt[i], k) << "\n";
      return;
    } else {
      k -= cnt[i];
    }
  }
  cout << 1;
}

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

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

using pii = pair<int, int>;

bool check(vector<vector<int>> a, vector<vector<int>> const &b) {
  int n = (int) a.size();
  for (int j = 0; j < n; j++) {
    if (a[0][j] != b[0][j]) {
      for (int i = 0; i < n; i++) {
        a[i][j] ^= 1;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int need_xor = (a[i][0] ^ b[i][0]);
    for (int j = 1; j < n; j++) {
      if (need_xor != (a[i][j] ^ b[i][j])) {
        return false;
      }
    }
  }
  return true;
}

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(n));
  vector<vector<int>> b(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < n; j++) {
      a[i][j] = s[j] - '0';
    }
  }
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < n; j++) {
      b[i][j] = s[j] - '0';
    }
  }

  for (int times = 0; times < 2; times++) {
    if (check(a, b)) {
      cout << "YES\n";
      return;
    }
    for (int j = 0; j < n; j++) {
      a[0][j] ^= 1;
    }
  }
  cout << "NO\n";
}

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

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

const int N = (int) 2e5 + 100;

int dp[N];
int cnt[N];

void solve() {
  int n;
  cin >> n;
  fill(dp, dp + N, 0);
  fill(cnt, cnt + N, 0);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  for (int i = 1; i < N; i++) {
    dp[i] += cnt[i];
    for (int j = 2 * i; j < N; j += i) {
      dp[j] = max(dp[j], dp[i]);
    }
  }
  cout << (n - *max_element(dp, dp + N)) << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int &e : v) {
    cin >> e;
  }
  int left = 0, right = n - 1;
  vector<int> ans(n);
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      ans[i] = v[left++];
    } else {
      ans[i] = v[right--];
    }
  }
  for (int i : ans) {
    cout << i << " ";
  }
  cout << "\n";
}

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

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  for (int i = 0; i <= 4; i++) {
    if (s.substr(0, i) + s.substr(n - 4 + i, 4 - i) == "2020") {
      cout << "YES" << endl;
      return;
    }
  }
  cout << "NO" << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int x;
  cin >> x;
  vector<int> ans;
  int sum = 0, last = 9;
  while (sum < x && last > 0) {
    ans.push_back(min(x - sum, last));
    sum += last;
    last--;
  }
  if (sum < x) {
    cout << -1 << "\n";
  } else {
    reverse(ans.begin(), ans.end());
    for (int i : ans) {
      cout << i;
    }
    cout << "\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;
  vector<ll> a(n);
  ll sum = 0;
  for (ll &x : a) {
    cin >> x;
    sum += x;
  }

  for (int i = n; i >= 1; i--) {
    if (sum % i == 0) {
      ll needSum = sum / i;
      ll curSum = 0;
      bool ok = true;
      for (int j = 0; j < n; j++) {
        curSum += a[j];
        if (curSum > needSum) {
          ok = false;
          break;
        } else if (curSum == needSum) {
          curSum = 0;
        }
      }

      if (ok) {
        cout << n - i << endl;
        return;
      }
    }
  }
}

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<ll> cnt(n + 1);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  ll ans = 0;
  for (int i = 2; i < n; i++) {
    ans += cnt[i - 1] * cnt[i] * cnt[i + 1];
  }
  for (int i = 1; i < n; i++) {
    ans += cnt[i] * (cnt[i] - 1) / 2 * cnt[i + 1];
  }
  for (int i = 2; i <= n; i++) {
    ans += cnt[i - 1] * cnt[i] * (cnt[i] - 1) / 2;
  }
  for (int i = 2; i < n; i++) {
    ans += cnt[i - 1] * cnt[i + 1] * (cnt[i + 1] - 1) / 2;
  }
  for (int i = 2; i < n; i++) {
    ans += cnt[i + 1] * cnt[i - 1] * (cnt[i - 1] - 1) / 2;
  }
  for (int i = 1; i <= n; i++) {
    ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
  }
  cout << ans << "\n";
}

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 300500;
const int mod = 1000000007;
ll fact[N];
ll invFact[N];

ll fast_pow(ll a, ll p) {
    ll res = 1;
    while (p) {
        if (p % 2 == 0) {
            a = (a * a) % mod;
            p /= 2;
        } else {
            res = (res * a) % mod;
            p--;
        }
    }
    return res;
}

ll C(int n, int k) {
    if (k > n) {
        return 0;
    }
    return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> v(n);
    for (ll &e : v) {
        cin >> e;
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int l = i + 1;
        int r = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin();
        ans = (ans + C(r - l, m - 1)) % mod;
    }
    cout << ans << "\n";
}

int main() {
    fact[0] = invFact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
        invFact[i] = fast_pow(fact[i], mod - 2);
    }
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    vector<int> L;
    vector<int> R;
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    for (auto &[l, r] : v) {
        cin >> l >> r;
        L.push_back(l);
        R.push_back(r);
    }
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    int ans = n - 1;
    for (auto [l, r] : v) {
        int left = lower_bound(R.begin(), R.end(), l) - R.begin();
        int right = max(0, n - (int)(upper_bound(L.begin(), L.end(), r) - L.begin()));
        ans = min(ans, left + right);
    }
    cout << ans << "\n";
}

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

#include <bits/stdc++.h>

using namespace std;

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

int solve(int a, int b) {
    int side = min(max(a * 2, b), max(a, b * 2));
    return side * side;
}

int main(int argc, char* argv[]) {
    int t;
    cin >> t;
    forn(tt, t) {
        int a, b;
        cin >> a >> b;
        cout << solve(a, b) << endl;
    }
}

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

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

	for (int tt = 0; tt < test; tt++) {
		int n;
		cin >> n;

		vector<int> a(n);

		for (int &x : a) {
			cin >> x;
		}

		sort(a.begin(), a.end());

		int result = a[n - 1] - a[0];

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				result = min(result, a[j] - a[i]);
			}
		}

		cout << result << endl;
	}

	return 0;
}

#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);
    int a = 0, b = 0;
    for (int &e : v) {
        cin >> e;
        if (e % 2 == 0) {
            a++;
        } else {
            b++;
        }
    }
    if (a % 2 != b % 2) {
        cout << "NO\n";
    } else {
        if (a % 2 == 0) {
            cout << "YES\n";
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (v[i] % 2 != v[j] % 2 && abs(v[i] - v[j]) == 1) {
                        cout << "YES\n";
                        return;
                    }
                }
            }
            cout << "NO\n";
        }
    }
}

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

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

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

	for (int tt = 0; tt < test; tt++) {
		int n, k;
		cin >> n >> k;

		int ans = n;

		for (int j = 1; j * j <= n; j++) {
			if (n % j == 0) {
				if (j <= k) {
					ans = min(ans, n / j);
				}

				if (n / j <= k) {
					ans = min(ans, j);
				}
			}
		}

		cout << ans << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

bool a[50][50];

int main() {
  int tests;
  cin >> tests;
  while (tests--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        char c;
        cin >> c;
        a[i][j] = c - '0';
      }
    }

    bool ans = true;
    for (int i = n - 2; i >= 0; --i) {
      for (int j = n - 2; j >= 0; --j) {
        if (a[i][j] && !a[i + 1][j] && !a[i][j + 1]) {
          ans = false;
        }
      }
    }

    cout << (ans ? "YES" : "NO") << endl;
  }
}

#include <bits/stdc++.h>

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    string ans = v[0];
    for (int j = 0; j < m; j++) {
        char save = ans[j];
        for (char d = 'a'; d <= 'z'; d++) {
            ans[j] = d;
            bool flag = true;
            for (int z = 0; z < n; z++) {
                int cntErrors = 0;
                for (int c = 0; c < m; c++) {
                    if (v[z][c] != ans[c]) {
                        cntErrors++;
                    }
                }
                if (cntErrors > 1) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cout << ans << endl;
                return;
            }
        }
        ans[j] = save;
    }
    cout << "-1" << endl;
}

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

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

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

  for (int tt = 0; tt < test; tt++) {
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    if (h * a != w * b) {
      cout << "NO" << endl;
      continue;
    }

    vector<vector<int>> result(h, vector<int>(w, 0));

    int shift = 0;

    for (shift = 1; shift < w; shift++) {
      if (shift * h % w == 0) {
        break;
      }
    }

    for (int i = 0, dx = 0; i < h; i++, dx += shift) {
      for (int j = 0; j < a; j++) {
        result[i][(j + dx) % w] = 1;
      }
    }

    cout << "YES" << endl;

    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cout << result[i][j];
      }

      cout << endl;
    }
  }

  return 0;
}

#include <bits/stdc++.h>

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

void solve() {
	ll m, n;
	cin >> n >> m;
	vector<ll> v(n);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (char c : s) {
			v[i] *= 2;
			v[i] += c - '0';
		}
	}
	ll need = ((1ll << m) - n - 1) / 2 + 1;
	ll cur = (1ll << (m - 1)) - 1;
	while (true) {
		ll left = cur + 1;
		bool flag = false;
		for (int i = 0; i < n; i++) {
			flag |= v[i] == cur;
			if (v[i] <= cur) {
				left--;
			}
		}
		if (left == need && !flag) {
			string s;
			for (int i = 0; i < m; i++) {
				s += (char)(cur % 2 + '0');
				cur /= 2;
			}
			reverse(s.begin(), s.end());
			cout << s << endl;
			return;
		} else if (left < need) {
			cur++;
		} else {
			cur--;
		}
	}
}

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

#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 a, b, c, r;
        cin >> a >> b >> c >> r;
        int L = max(min(a, b), c - r);
        int R = min(max(a, b), c + r);
        cout << max(a, b) - min(a, b) - max(0, R - L) << endl;
    }
}

#include <bits/stdc++.h>

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

int main() {
    int cntTest;
    cin >> cntTest;
    for (int test = 0; test < cntTest; test++) {
        int n, p, k;
        cin >> n >> p >> k;
        int pref = 0;
        int ans = 0;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        for (int i = 0; i <= k; i++) {
            int sum = pref;
            if (sum > p) break;
            int cnt = i;
            for (int j = i + k - 1; j < n; j += k) {
                if (sum + a[j] <= p) {
                    cnt += k;
                    sum += a[j];
                } else {
                    break;
                }
            }
            pref += a[i];
            ans = max(ans, cnt);
        }
        cout << ans << "\n";
    }
}

#include <bits/stdc++.h>

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

int main() {
    int cntTest;
    cin >> cntTest;
    for (int test = 0; test < cntTest; test++) {
        ll n, t, a, b;
        cin >> n >> t >> a >> b;
        vector<pair<ll, ll>> v;
        vector<int> hard(n);
        int cntA = 0, cntB = 0;
        for (int i = 0; i < n; i++) {
            cin >> hard[i];
            if (hard[i]) {
                cntB++;
            } else {
                cntA++;
            }
        }
        for (int i = 0; i < n; i++) {
            ll time;
            cin >> time;
            v.push_back({time, hard[i]});
        }
        v.push_back({t + 1, 0});
        sort(v.begin(), v.end());
        ll cnt1 = 0, cnt2 = 0;
        ll ans = 0;
        for (int i = 0; i <= n; i++) {
            ll need = cnt1 * a + cnt2 * b;
            ll has = v[i].first - 1 - need;
            if (has >= 0) {
                ll canA = min((cntA - cnt1), has / a);
                has -= canA * a;
                ll canB = min((cntB - cnt2), has / b);
                ans = max(ans, cnt1 + cnt2 + canA + canB);
            }
            int l = i;
            while (l < v.size() && v[l].first == v[i].first) {
                if (v[l].second) {
                    cnt2++;
                } else {
                    cnt1++;
                }
                l++;
            }
            i = l - 1;
        }
        cout << ans << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
 
int f(string s) {
    cout << s << endl;
    int w;
    cin >> w;
    if (w == 0)
        exit(0);
    return w;
}
 
int main() {
    const int N = 300;
    int st = f(string(N, 'a'));
    int n = 2 * N - (st + f(string(N, 'b')));
    string t(n, 'a');
    int A = N - st, B = n - A;
    st = B;
    for (int i = 0; i < n - 1; i++) {
        t[i] = 'b';
        if (f(t) > st)
            t[i] = 'a';
        else
            st--;
    }
    if (st)
        t.back() = 'b';
    f(t);
}

#include <bits/stdc++.h>

using namespace std;

void dfs_order(int u, int p, vector<vector<int>> const& g, vector<int> &order) {
    for (auto v : g[u]) {
        if (v != p) {
            dfs_order(v, u, g, order);
        }
    }
    order.push_back(u);
}

void get_order(map<pair<int, int>, vector<int>> const& in, int n, vector<int> &order) {
    vector<vector<int>> g(n);
    for (auto e : in) {
        auto vs = e.second;

        if (vs.size() == 2) {
            g[vs[0]].push_back(vs[1]);
            g[vs[1]].push_back(vs[0]);
        }
    }

    dfs_order(0, -1, g, order);
}

void dfs_polygon(int u, vector<vector<int>> const& g, vector<bool> &used, vector<int> &res) {
    if (used[u]) {
        return;
    }
    used[u] = true;
    res.push_back(u);
    for (auto e : g[u]) {
        dfs_polygon(e, g, used, res);
    }
}

void get_polygon(map<pair<int, int>, vector<int>> const& in, int n, vector<int> &polygon) {
    vector<vector<int>> g(n);
    for (auto e : in) {
        if (e.second.size() == 1) {
            auto edge = e.first;
            g[edge.first].push_back(edge.second);
            g[edge.second].push_back(edge.first);
        }
    }

    vector<bool> used(n);
    dfs_polygon(0, g, used, polygon);
}

void get_polygon(vector<vector<int>> const& in, int n, vector<int> const& order, vector<int> &polygon) {
    vector<pair<int, int>> listp(n, {-1, -1});
    auto last = in[order.back()];
    for (int i = 0; i < 3; i++) {
        listp[last[i]] = {last[(i + 1) % 3], last[(i + 2) % 3]};
    }

    for (int i = (int) order.size() - 2; i >= 0; i--) {
        auto x = in[order[i]];

        int j = 0;
        while (listp[x[j]] != pair<int, int>{-1, -1}) {
            j++;
        }

        int x1 = x[j], x2 = x[(j + 1) % 3], x3 = x[(j + 2) % 3];
        if (listp[x2].second != x3) {
            swap(x2, x3);
        }

        listp[x1] = {x2, x3};
        listp[x2].second = x1;
        listp[x3].first = x1;
    }

    polygon.push_back(0);

    int now = listp[0].second;
    while (now != 0) {
        polygon.push_back(now);
        now = listp[now].second;
    }
}

void out(vector<int> const& v) {
    for (auto e : v) {
        cout << e + 1 << ' ';
    }
    cout << endl;
}

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> in(n - 2, vector<int>(3));
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> in[i][j];
            in[i][j]--;
        }
        sort(in[i].begin(), in[i].end());
    }

    map<pair<int, int>, vector<int>> mp;
    for (int i = 0; i < n - 2; i++) {
        auto tri = in[i];
        for (int j = 0; j < 2; j++) {
            for (int k = j + 1; k < 3; k++) {
                mp[{tri[j], tri[k]}].push_back(i);
            }
        }
    }

    vector<int> order;
    get_order(mp, n, order);

    vector<int> polygon;
    get_polygon(in, n, order, polygon);
    // get_polygon(mp, n, polygon);  // another solution

    out(polygon);
    out(order);
}

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

    for (int t_num = 1; t_num <= t; t_num++) {
        solve();
    }

    return 0;
}