/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
//#define cout file

vector<int> generateBinaryOnes() {
    vector<int> ones;
    int limit = 2 * 1e9;
    int power = 1;
    while (true) {
        int val = (1 << power) - 1;
        if (val > limit) break;
        ones.push_back(val);
        power++;
    }
    return ones;
}

int findMaxProduct(const vector<int>& nums) {
    vector<int> ones = generateBinaryOnes();
    unordered_set<int> numSet(nums.begin(), nums.end());
    
    for (int num : nums) {
        for (int target : ones) {
            int diff = target - num;
            if (numSet.count(diff)) {
                return 1;
            }
        }
    }
    return 0;
}

void solve(int tc) {
    // string outp = "output"+to_string(tc)+".txt";
    // string inp = "input"+to_string(tc)+".txt";
    // ofstream file(outp);
    // freopen(inp.c_str(),"r",stdin);
    int t; cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<int> arr(n);
        for(int i=0; i<n; ++i){
            cin >> arr[i];
        }
        cout << findMaxProduct(arr) << endl;
    }
}

int main()
{
    int l=0;
    int r=0;
    for(int i=l;i<=r;i++) solve(i);
}