from collections import Counter
from collections import defaultdict
def solve_test_case(n, numbers):
cnt = defaultdict(int)
res=0
d= (1<<31)-1
for nb in numbers:
inv=d^nb
if cnt[inv]>0:
cnt[inv]-=1
else:
cnt[nb]+=1
res+=1
return res
if __name__ == "__main__":
t = int(input())
test_cases = []
for _ in range(t):
n = int(input())
numbers = list(map(int, input().split()))
print(solve_test_case(n, numbers))#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int>a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int v=(1<<31)-1;
map<int, vector<int>>mp;
for (int i = 0; i < n; i++) {
mp[a[i]].push_back(i);
}
vector<int>visited(n, 0);
for (int i = 0; i < n; i++) {
if (visited[i])continue;
int number = a[i]^v;
if (mp[number].size() > 0 && mp[a[i]].size() > 0) {
int s1 = mp[number].size();
int s2 = mp[a[i]].size();
int mn = min(s1, s2);
while (mn--) {
int l = mp[a[i]].back();
visited[l] = 1;
mp[a[i]].pop_back();
int index = mp[number].back();
visited[index] = 1;
mp[number].pop_back();
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (visited[i] == 1) {
count++;
}
}
int remaining = n - count;
int ans = remaining + count / 2;
cout << ans << endl;
}
int main()
{
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
int t;
cin >> t;
while (t--) {
solve();
}
}470. Implement Rand10() Using Rand7() | 866. Prime Palindrome |
1516A - Tit for Tat | 622. Design Circular Queue |
814. Binary Tree Pruning | 791. Custom Sort String |
787. Cheapest Flights Within K Stops | 779. K-th Symbol in Grammar |
701. Insert into a Binary Search Tree | 429. N-ary Tree Level Order Traversal |
739. Daily Temperatures | 647. Palindromic Substrings |
583. Delete Operation for Two Strings | 518. Coin Change 2 |
516. Longest Palindromic Subsequence | 468. Validate IP Address |
450. Delete Node in a BST | 445. Add Two Numbers II |
442. Find All Duplicates in an Array | 437. Path Sum III |
436. Find Right Interval | 435. Non-overlapping Intervals |
406. Queue Reconstruction by Height | 380. Insert Delete GetRandom O(1) |
332. Reconstruct Itinerary | 368. Largest Divisible Subset |
377. Combination Sum IV | 322. Coin Change |
307. Range Sum Query - Mutable | 287. Find the Duplicate Number |