#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll t;
    cin>>t;

    set <ll> poss;
    poss.insert(0);
    ll num=1;
    while (num<=(10000000000))  // 10 zeroes after 1.
    {
        poss.insert(num);
        num*=2;
    }

    while (t--)
    {
        ll n;
        cin>>n;
        vector <ll> v(n+2);
        for (ll i=1;i<=n;i++)
        {
            cin>>v[i];
        }
        ll answer=0;
        for (ll i=1;i<=n;i++)
        {
            if (poss.count(v[i])!=0)
            {
                answer++;
            }
        }
        cout<<answer<<"\n";
    }

    return 0;
}