#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

const int N = 1e8;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++) {
        int pow2 = 2;
        while(pow2 <= N) {
            int a = v[i];
            int b = (pow2 - 1) - a;
            if(a == b) {
                auto it1 = lower_bound(v.begin(), v.end(), a);
                auto it2 = upper_bound(v.begin(), v.end(), b);
                if(it2 - it1 > 1) {
                    cout << 1 << endl;
                    return;
                }
            }
            else {
                if(binary_search(v.begin(), v.end(), b)) {
                    cout << 1 << endl;
                    return;
                }
            }
            pow2 *= 2;
        }
    }
    cout << 0 << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}