/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t; cin >> t; while(t--)
    {
        int n; cin >> n;
        int a[n];
        map<int,bool> mp;
        for(int i=0;i<n;i++) cin >> a[i], mp[a[i]]=true;
        int target;
        bool ok = false;
        for(int bit=1;bit<=30;bit++)
        {
            target = (1<<bit)-1;
            for(int i=0;i<n;i++)
            {
                if(mp[target-a[i]])
                {
                    ok = true;
                    cout<<1<<'\n';
                    break;
                }
            }
            if(ok) break;
        }
        if(!ok) cout<<0<<'\n';
    }
}