L56GAME

#include <iostream>
using namespace std;

int main() {
  int test_cases,n,odd,even,k,i,found,o,e;
  
  cin>>test_cases;
  
  while(test_cases--)
  {
    cin>>n;
    odd=0;
    even=0;
    found=0;
    for(i=0;i<n;i++)
    {
      cin>>k;
      
      if(k%2==0)
      {
        even++;
      }
      else
      {
        odd++;
      }
    }
    o=e=0;
     if(odd==1)
    {
      o=1;
    }
    else if(odd==0)
    {
      o=0;
    }
    else if(odd%2==0 && odd>0)
    {
      e=1;
    }
    else
    {
      e=1;
      o=1;
    }
    
    if(even>0 && e==0)
    { e=1;}
   
    
    
    
    cout<<o+e<<endl;
  }
}