#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    int p = (n + 1) / 2 - 1;
    int res = std::count(a.begin() + p, a.end(), a[p]);
    std::cout << res << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int S = 0, sum = 0;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        cur += a[i];
        cur = max(cur, 0LL);
        S = max(S, cur);
    }
    sum = (sum % P + P) % P;
    S = S % P;
    int t = 1;
    for (int i = 0; i < k; i++) {
        t = t * 2 % P;
    }
    int ans = (sum + S * t - S + P) % P;
    cout << ans << '\n';
}


signed main() {
    //cout << fixed << setprecision(20);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1, G = 1;
    //cin >> G;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int v, u;
        std::cin >> v >> u;
        --v, --u;
        adj[v].emplace_back(u);
        adj[u].emplace_back(v);
    }
    auto check = [&](int x) {
        int res = 0;
        auto dfs = [&](auto self, int v, int f) -> int {
            int sz = 1;
            for (int u : adj[v]) {
                if (u == f) {
                    continue;
                }
                sz += self(self, u, v);
            }
            if (sz >= x && f != v) {
                ++res, sz = 0;
            }
            return sz;
        };
        int t = dfs(dfs, 0, 0);
        return (res > k || (t >= x && res == k) ? true : false);
    };
    int low = 1, high = n / (k + 1) + 1;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    std::cout << low << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
#define int ll
#define all(a) a.begin(), a.end()
 
void solve() {
    int n, x;
    cin >> n >> x;
    ++x;
    vector<int> a(n);
    for (int &i: a)
        cin >> i;
    int res = -1;
    for (int i = 30; i >= 0; --i) {
        vector<int> b;
        bool open = false;
        for (int j = 0; j < a.size(); ++j) {
            if (!open)
                b.push_back(a[j]);
            else
                b.back() ^= a[j];
            if (a[j] & (1 << i))
                open = !open;
        }
        if (!(x & (1 << i))) {
            if (open) {
                cout << res << '\n';
                return;
            }
            a = b;
        } else {
            if (!open)
                res = max(res, (int) b.size());
        }
    }
    cout << res << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
int const maxn = 1e5 + 5;
int a[maxn];
 
int solve(int n, int x) {
    int res = 0, curr = 0;
    for (int i = 1; i <= n; i++) {
        curr ^= a[i];
        if ((curr|x) == x) curr = 0, res++;
        else {
            if (i == n) return -1;
        }
    }
    return res;
}
 
main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        for (int i = 1; i <= n; i++) cin >> a[i];
        int ans = -1;
        ans = max(ans, solve(n, x));
        for (int b = 29; b >= 0; b--) {
            if ((x>>b)&1) {
                int y = (x^(1 << b));
                for (int c = b - 1; c >= 0; c--) {
                    if (((y>>c)&1) == 0) y ^= (1 << c);
                }
                ans = max(ans, solve(n, y));
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define int long long
const int N = 200200, P = 1e9 + 7;
int fact[N], reverse_fact[N];

int binpow(int x, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    int t = binpow(x, n / 2);
    t = t * t % P;
    if (n % 2 == 1)
        t = t * x % P;
    return t;
}

int inv(int x) {
    return binpow(x, P - 2);
}

void precalc() {
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % P;
    for (int i = 0; i < N; i++)
        reverse_fact[i] = inv(fact[i]);
}

int C(int n, int k) {
    return fact[n] * reverse_fact[k] % P * reverse_fact[n - k] % P;
}

int f(int a, int b) {
    return C(a + b, b);
}

vector<vector<int>> g;
vector<int> dp, siz;

void dfs(int v) {
    int cnt = 0, x = -1, y = -1;
    for (auto to : g[v]) {
        dfs(to);
        siz[v] += siz[to];
        if (siz[to] == 1)
            cnt++;
        else if (x == -1)
            x = to;
        else
            y = to;
    }
    if (x == -1)
        dp[v] = fact[cnt];
    else if (y == -1)
        dp[v] = dp[x] * fact[cnt] % P * f(siz[x], cnt) % P;
    else
        dp[v] = dp[x] * dp[y] % P * f(siz[x], siz[y]) % P;
}


void solve() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<int> pref(m1), suf(m2);
    for (auto &it : pref)
        cin >> it;
    for (auto &it : suf)
        cin >> it;
    for (auto &it : pref)
        it--;
    for (auto &it : suf)
        it--;
    g.assign(n, {});
    dp.assign(n, 1);
    siz.assign(n, 1);
    if (pref.back() != suf.front() || pref.front() != 0 || suf.back() != n - 1) {
        cout << 0 << '\n';
        return;
    }
    for (int i = m1 - 1; i > 0; i--) {
        g[pref[i]].eb(pref[i - 1]);
        for (int j = pref[i] - 1; j > pref[i - 1]; j--)
            g[pref[i - 1]].eb(j);
    }
    for (int i = 0; i < m2 - 1; i++) {
        g[suf[i]].eb(suf[i + 1]);
        for (int j = suf[i] + 1; j < suf[i + 1]; j++)
            g[suf[i + 1]].eb(j);
    }
    dfs(pref.back());
    cout << dp[pref.back()] << '\n';
}


signed main() {
    //cout << fixed << setprecision(20);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1, G;
    //cin >> G;
    precalc();
    cin >> T;
    while (T--)
        solve();
    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;

template<class Info>
struct Fenwick {
    std::vector<Info> t;
    int n;
    
    Fenwick(int n = 0) : n(n) {
        t.resize(n);
    }
    
    void add(int x, const Info &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            t[i - 1] = t[i - 1] + v;
        }
    }
    
    Info sum(int x) {
        x++;
        Info res = Info();
        for (int i = x; i > 0; i -= i & -i) {
            res = res + t[i - 1];
        }
        return res;
    }
    
    Info rangeSum(int l, int r) {
        Info res = sum(r) - sum(l - 1);
        return res;
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n), pos(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::reverse(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        pos[a[i]] = i;
    }
    constexpr int K = 19;
    std::vector<i64> res(q);
    std::vector<std::vector<std::pair<int, int>>> qry(n);
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        l--, r--;
        std::swap(l, r);
        l = n - l - 1;
        r = n - r - 1;
        qry[r].emplace_back(l, i);
    }
    std::vector<i64> dp(n + 1);
    Fenwick<i64> f(n);
    for (int r = 0; r < n; r++) {
        int x = a[r];
        dp[x] = 1;
        // n * log(n) * log(n)
        for (int y = x; y <= n; y += x) {
            if (pos[y] > pos[x]) {
                continue;
            }
            for (int z = 2 * y; z <= n; z += y) {
                if (pos[z] > pos[y]) {
                    continue;
                }
                dp[z] += dp[y];
            }
        }
        // n * log(n) * log(n)
        for (int y = x; y <= n; y += x) {
            f.add(pos[y], dp[y]);
            dp[y] = 0;
        }
        // q * log(n)
        for (auto [l, i] : qry[r]) {
            res[i] += f.rangeSum(l, r);
        }
    }
    for (int i = 0; i < q; i++) {
        std::cout << res[i] << " \n"[i == q - 1];
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
}