#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    sort(x.begin(), x.end());
    if (x[0] % 2 == x[n - 1] % 2) {
        cout << 0 << endl;
        return;
    }
    int left = n, right = n;
    for (int i = 1; i < n; ++i) {
        if (x[i] % 2 != x[0] % 2) {
            left = i;
            break;
        }
    }
    for (int i = 1; i < n; ++i) {
        if (x[n - i - 1] % 2 != x[n - 1] % 2) {
            right = i;
            break;
        }
    }
    cout << min(left, right) << '\n';
}

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

#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int>>;
using pii = pair<int, int>;

void solve() {
  string s;
  cin >> s;
  int n = s.size();
  int bal = 0;
  for (int i = 1; i + 1 < n; i++) {
    if (s[i] == '(') bal++;
    else bal--;
    if (bal < 0) {
      cout << "YES\n";
      return;
    }
  }
  if (bal == 0) {
    cout << "NO\n";
  } else {
    cout << "YES\n";
  }
}

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

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (auto &x : d) {
        cin >> x;
    }
    vector<int> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    int left = 0;
    vector<int> last;
    for (int i = 0; i < n; ++i) {
        if (d[i] == -1) {
            last.push_back(i);
        } else {
            left += d[i];
        }
        while (left < l[i]) {
            if (last.empty()) {
                cout << -1 << '\n';
                return;
            }
            d[last.back()] = 1;
            ++left;
            last.pop_back();
        }
        while (left + last.size() > r[i]) {
            if (last.empty()) {
                cout << -1 << '\n';
                return;
            }
            d[last.back()] = 0;
            last.pop_back();
        }
    }
    for (auto &x : d) {
        cout << max(0, x) << " ";
    }
    cout << "\n";
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 11;

struct edge {
    int t, w;
    edge(int t, int w) : t(t), w(w) {}
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> b(n);
    for (auto &x : b) {
        cin >> x;
    }
    vector<vector<edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int s, t, w;
        cin >> s >> t >> w;
        --s; --t;
        graph[s].push_back(edge(t, w));
    }
    auto check = [&](int maxW) {
        vector<int> best(n, 0);
        for (int i = 0; i < n; ++i) {
            if (i > 0 && best[i] == 0) {
                continue;
            }
            best[i] += b[i];
            best[i] = min(best[i], maxW);
            for (auto p : graph[i]) {
                if (p.w <= best[i]) {
                    best[p.t] = max(best[p.t], best[i]);
                }
            }
        }
        return (best.back() > 0);
    };
    if (!check(INF)) {
        cout << -1 << endl;
        return;
    }
    int l = 0, r = INF;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<set<int>> graph;
vector<int> ans;

void dfs(int v) {
    while (!graph[v].empty()) {
        int u = *graph[v].begin();
        graph[u].erase(v);
        graph[v].erase(u);
        dfs(u);
    }
    ans.push_back(v);
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        graph.clear();
        ans.clear();
        int n;
        cin >> n;
        map<int, int> p, v;
        map<pair<int, int>, int> toIndex;
        vector<pair<int, int>> part;
        for (int i = 1; i <= n; ++i) {
            int volume, pitch;
            cin >> volume >> pitch;
            toIndex[make_pair(volume, pitch)] = i;
            if (p.count(pitch) == 0) {
                p[pitch] = graph.size();
                graph.push_back(set<int>());
                part.push_back(make_pair(0, pitch));
            }
            if (v.count(volume) == 0) {
                v[volume] = graph.size();
                graph.push_back(set<int>());
                part.push_back(make_pair(volume, 0));
            }
            graph[v[volume]].insert(p[pitch]);
            graph[p[pitch]].insert(v[volume]);
        }
        int root = 0;
        int cnt = 0;
        for (int i = 0; i < graph.size(); ++i) {
            if (graph[i].size() % 2 == 1) {
                ++cnt;
                root = i;
            }
        }
        dfs(root);
        if (ans.size() != n + 1 || cnt > 2) {
            cout << "NO" << endl;
            continue;
        }
        vector<int> out;
        for (int i = 0; i < n; ++i) {
            auto p1 = part[ans[i]];
            auto p2 = part[ans[i + 1]];
            out.push_back(toIndex[make_pair(p1.first + p2.first, p1.second + p2.second)]);
            if (out[i] == 0) {
                out.clear();
                break;
            }
        }
        if (out.empty()) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
            for (int i = 0; i < n; ++i) {
                cout << out[i] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int f(int x, int y) {
    return (x % y) + (y % x);
}

void Solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    int mx = a[0];
    for (int i = 0; i < n; ++i) {
        ans = max(ans, f(mx, a[i]));
        if (a[i] > mx) {
            if (a[i] >= mx * 2) {
                mx = a[i];
                for (int j = 0; j < i; ++j) {
                    ans = max(ans, f(a[i], a[j]));
                }
            } else {
                mx = a[i];
                ans = mx;
            }
        }
        cout << ans << ' ';
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        Solve();
    }
    return 0;
}