#include<bits/stdc++.h>

#define ll long long
#define endl "\n"
#define pb push_back
#define printv for(auto e:v) cout << e << " ";  cout << endl;
#define printmp for(auto [x,y]:mp) cout << x << " " << y << endl; cout << endl;

using namespace std;

void solve(){
    ll n;   cin >> n;
    vector<ll>ar(n);
    for(int i=0;i<n;i++)    cin >> ar[i];
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            ll sum = ar[i] + ar[j];
            int p = (sum & (sum+1));
            //cout << ar[i] <<  " " << ar[j] << " " << p << endl;
            if(!p){
                cout << 1 << endl;
                return;
            }

        }
    }
    cout << 0 << endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;  cin >> t;
    while(t--){
        solve();
    }
    return 0;
}