#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 i64 = long long;
 
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % P)} {}
    
    constexpr int norm(int x) const {
        if (x < 0) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(P - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    constexpr MInt &operator*=(MInt rhs) {
        x = 1LL * x * rhs.x % P;
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
constexpr int MOD = 1e9 + 7;
using Z = MInt<MOD>;
 
namespace comb {
    int n = 0;
    std::vector<Z> _fac = {1};
    std::vector<Z> _invfac = {1};
    std::vector<Z> _inv = {0};
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int m, int k) {
        if (m < k || k < 0) return 0;
        return fac(m) * invfac(k) * invfac(m - k);
    }
} // namespace comb
 
void solve() {
    int n, m1, m2;
    std::cin >> n >> m1 >> m2;
    std::vector<int> p(m1), s(m2);
    for (int i = 0; i < m1; i++) {
        std::cin >> p[i];
    }
    for (int i = 0; i < m2; i++) {
        std::cin >> s[i];
    }
    if (p[0] != 1 || s[0] != p[m1 - 1] || s[m2 - 1] != n) {
        std::cout << "0\n";
        return;
    }
    Z res = comb::binom(n - 1, s[0] - 1);
    for (int i = m1 - 2; i > -1; i--) {
        res *= comb::binom(p[i + 1] - 2, p[i + 1] - p[i] - 1) * comb::fac(p[i + 1] - p[i] - 1);
    }
    for (int i = 1; i < m2; i++) {
        res *= comb::binom(n - s[i - 1] - 1, s[i] - s[i - 1] - 1) * comb::fac(s[i] - s[i - 1] - 1);
    }
    std::cout << res << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    #ifndef ONLINE_JUDGE
        freopen("/home/q1n/coding/input.txt", "r", stdin);
        freopen("/home/q1n/coding/output.txt", "w", stdout);
    #else
        // online submission
    #endif
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

#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();
    }
}