/**
 Author : Kamonasish Roy (Bullet)
 Time : 2025-02-25 13:03:09
 **/

#include<bits/stdc++.h>
using namespace std;
const long long M=5e5,MOD=1e9+7;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    assert(t>=1 && t<=10000);
    int sumofn=0;
    while(t--){
    	int n;
    	cin>>n;
    	assert(n> 1 && n<=200000);
    	int f=0;
    	map<int,int>mp;
    	vector<int>arr(n+1);
    	for(int i=1;i<=n;i++){
    		int a;
    		cin>>a;
    		assert(a >= 1&& a<=1e8);
    		mp[a]++;
    		arr[i]=a;
    	}
    	int cur=4;
    	while(cur<=2e8 && !f){
    		int bit=cur-1;// we need to check 2^i - 1. if sum is availbale then possible 1.
    		for(int i=1;i<=n;i++){
    			int rem=bit-arr[i];
    			if(mp.count(rem)){
    				f=1;
    				break;
    			}
    		}
    		cur*=2;
    	}
    	sumofn+=n;
    	assert(sumofn>1 && sumofn<=2e5);
    	cout<<f<<"\n";
    	
    	
    	
    	}
    	
    	   
    return 0;
 
}