#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

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;
}

int main() {
    int tc;
    cin>>tc;
while(tc--){
int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; ++i){
        cin >> arr[i];
    }
    cout << findMaxProduct(arr) << endl;
}
}