https://codeforces.com/contest/2026/problem/E
最大权值闭合子图：有一个图，里面的点权值或正或负或零。需要找出一个权值最大的子图，且使得子图中每个点的后继都在子图中。
$$权值和=所有正值之和 - 未选择的正值之和 + 选中的负值之和$$
假设我们一开始拥有所有正值，当我们在此基础上不选择一个正值时，我们需要支付其权值的惩罚，当我们选择一个负值时，我们需要支付其权值的代价。当我们选择一个值时，必须选中其后继。
即最小化：不选择的正值 + 选中的负值的绝对值。代入最小割模型，一方面我们需要让这两部分为割，另一方面，对于点与点直接的边，因为必须选择，我们需要将其置为inf，使得其在最小割中一定不成为割边。
于是建模：设一个源点s，与所有的正值相连，边权为其点权。设一个汇点t，由所有的负值点指向，边权为其点权的绝对值。
这样当一个正值点不被选择时，它一定在T中，s与其的连边成为割边。当一个负值点被选择时，它一定在s中，它与t点的连边成为割边。此时求一个最小割，即能最大化所选的权值和。

E题题解

如果选了一个数，可以获得价值1，但是必须要支付其二进制所含1数量的价值（重复的则可以不支付），因此原数组的点可以视作权值1的点，设一个源点s指向。每个二进制位可以视作权值-1的点，指向一个汇点t。原数组点i与其对应位为1的二进制位连线，边权为INF。答案为n-最小割。

#include<bits/stdc++.h>

#define MULTI_TEST

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

constexpr ll inf = 1E9;
template<class T>
struct MaxFlow {
    struct _Edge {
        int to;
        T cap;
        _Edge(int to, T cap) : to(to), cap(cap) {}
    };

    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;

    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }

    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }

    std::vector<bool> minCut() {
        std::vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }

    struct Edge {
        int from;
        int to;
        T cap;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

int n;
void solve(){
    cin>>n;
    MaxFlow<int> mf(n+62);
    int s = n+60, t = n+61;
    for(int i=0;i<n;i++){
        mf.addEdge(s,i,1);
        ll x;
        cin>>x;
        bitset<60> b(x);
        for(int j=0;j<60;j++){
            if(b[j]==1)
                mf.addEdge(i,n+j,inf);
        }
    }
    for(int i=0;i<60;i++) mf.addEdge(n+i,t,1);
    cout<<n - mf.flow(s,t)<<endl;

}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}