#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mod=998244353;
const ll INF = -10000000000000;
 
void solve() {
   int n;
   cin >> n;
   vector<int> a(n),even,odd;
   for(int i=0;i<n;i++){ 
   cin >> a[i];
   if(a[i]%2==0) even.push_back(a[i]);
   else odd.push_back(a[i]);}
   int cnt=0,it=0;
   for(int i=0;i<n;i++){
    if(i%2==0 && cnt<even.size()) a[i]=even[cnt++];
    else if(i%2==0) a[i]=odd[it++];
    else if(i%2==1 && it<odd.size()) a[i]=odd[it++];
    else if(i%2==1) a[i]=even[cnt++];
   }
   ll sum = 0;
   int ans = 0;
   for(int i=0;i<n;i++){
    sum+=a[i];
    if(sum%2==0){
        ans++;
        while(sum%2==0) sum/=2;
    }
   }
   cout << ans << '\n';
}
 
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) solve();
 
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwpjb25zdCBpbnQgTW9kPTk5ODI0NDM1MzsKY29uc3QgbGwgSU5GID0gLTEwMDAwMDAwMDAwMDAwOwoKdm9pZCBzb2x2ZSgpIHsKICAgaW50IG47CiAgIGNpbiA+PiBuOwogICB2ZWN0b3I8aW50PiBhKG4pLGV2ZW4sb2RkOwogICBmb3IoaW50IGk9MDtpPG47aSsrKXsgCiAgIGNpbiA+PiBhW2ldOwogICBpZihhW2ldJTI9PTApIGV2ZW4ucHVzaF9iYWNrKGFbaV0pOwogICBlbHNlIG9kZC5wdXNoX2JhY2soYVtpXSk7fQogICBpbnQgY250PTAsaXQ9MDsKICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICBpZihpJTI9PTAgJiYgY250PGV2ZW4uc2l6ZSgpKSBhW2ldPWV2ZW5bY250KytdOwogICAgZWxzZSBpZihpJTI9PTApIGFbaV09b2RkW2l0KytdOwogICAgZWxzZSBpZihpJTI9PTEgJiYgaXQ8b2RkLnNpemUoKSkgYVtpXT1vZGRbaXQrK107CiAgICBlbHNlIGlmKGklMj09MSkgYVtpXT1ldmVuW2NudCsrXTsKICAgfQogICBsbCBzdW0gPSAwOwogICBpbnQgYW5zID0gMDsKICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICBzdW0rPWFbaV07CiAgICBpZihzdW0lMj09MCl7CiAgICAgICAgYW5zKys7CiAgICAgICAgd2hpbGUoc3VtJTI9PTApIHN1bS89MjsKICAgIH0KICAgfQogICBjb3V0IDw8IGFucyA8PCAnXG4nOwp9CgppbnQgbWFpbigpeyAKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CgkKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICB3aGlsZSAodC0tKSBzb2x2ZSgpOwogICAgCgogICAgcmV0dXJuIDA7Cn0K

NQoxCjEKMgoxIDIKMwoyIDQgNgo0CjEwMDAwMDAwMDAgOTk5OTk5OTk5IDk5OTk5OTk5OCA5OTk5OTk5OTcKMTAKMyAxIDQgMSA1IDkgMiA2IDUgMwo=

5
1
1
2
1 2
3
2 4 6
4
1000000000 999999999 999999998 999999997
10
3 1 4 1 5 9 2 6 5 3