There are n block towers in a row, where tower i has a height of a_i. You're part of a building crew, and you want to make the buildings look as nice as possible. In a single day, you can perform the following operation:

  * Choose two indices i and j (1 ≤ i, j ≤ n; i ≠ j), and move a block from tower i to tower j. This essentially decreases a_i by 1 and increases a_j by 1. 



You think the ugliness of the buildings is the height difference between the tallest and shortest buildings. Formally, the ugliness is defined as max(a)-min(a). 

What's the minimum possible ugliness you can achieve, after any number of days?

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t cases follow.

The first line of each test case contains one integer n (2 ≤ n ≤ 100) — the number of buildings.

The second line of each test case contains n space separated integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7) — the heights of the buildings.

Output

For each test case, output a single integer — the minimum possible ugliness of the buildings.

Example

Input


3
3
10 10 10
4
3 2 1 2
5
1 2 3 1 5


Output


0
0
1

Note

In the first test case, the ugliness is already 0.

In the second test case, you should do one operation, with i = 1 and j = 3. The new heights will now be [2, 2, 2, 2], with an ugliness of 0.

In the third test case, you may do three operations: 

  1. with i = 3 and j = 1. The new array will now be [2, 2, 2, 1, 5], 
  2. with i = 5 and j = 4. The new array will now be [2, 2, 2, 2, 4], 
  3. with i = 5 and j = 3. The new array will now be [2, 2, 3, 2, 3]. 

The resulting ugliness is 1. It can be proven that this is the minimum possible ugliness for this test.
/*
  shadril238
*/

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// policy Based ds
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
typedef tree<long long , null_type, less_equal<long long>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 
#define order(s, x) s.order_of_key(x)
#define elemat(s ,x) s.find_by_order(x)
 

typedef   vector<ll>  vi;
typedef   vector<pair<ll, ll>> vii;
typedef   multiset<pair<ll, ll>> msii;
typedef   multiset<ll> msi;
typedef   set<pair<ll, ll>> sii;
typedef   set<ll> si;
typedef   map<ll, ll> mii;
 
#define frac(x)       cout.unsetf(ios::floatfield); cout.precision(x); cout.setf(ios::fixed,ios::floatfield);
#define recap(i,k,n)  for(int i = k; i>=n; i--)
#define rep(i,k,n)      for(int i=k; i<n; i++)
#define shadril238       ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define for1(x, a, b)    for(x=a; x<b; x++)
#define for2(x, a, b)    for(x=a, x>=b; x--)
#define endl       "\n"
#define all(x)      x.begin(), x.end()
#define mp          make_pair
#define read        freopen("input.txt","r",stdin)
#define write       freopen("output.txt","w",stdout)
#define pb          push_back
#define ff          first
#define ss          second
#define bb          begin
#define mem(arr, x)   memset(arr, x, sizeof(arr));
#define arr_ub(arr, n, x) upper_bound(arr, arr+n, x)-arr
#define arr_lb(arr, n, x) lower_bound(arr, arr+n, x)-arr
#define u_p(v, x)     upper_bound(v.begin(), v.end(), x)-v.begin()
#define l_b(v, x)     lower_bound(v.begin(), v.end(), x)-v.begin()
 
 
const ll sz=1e6+123;
#define INF 1000000000000000007
#define MOD 1000000007
#define stringLen 18446744073709551620
#define pi 3.1415926536
 
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
 
 
//vi divisorList[sz];
//ll divisorNumber[sz];
//void findDivisor(ll n){
//    for(ll i=1; i<=n; i++){
//      for(ll j=i; j<=n; j+=i){
//         divisorList[j].pb(i);
//            divisorNumber[j]++;
//      }
//    }
//}
 
//bool isPalindrome(string s){ll i=0,j=s.size()-1;for(i,j;i<=j;i++,j--){if(s[i]!=s[j]) return 0;}return 1;}
//ll gcd(ll a, ll  b){return b==0? a: gcd(b, a%b);}
//// lcm * gcd = a*b
//ll lcm(ll a, ll b){if(a>b)swap(a, b);return a*(b/gcd(a, b));}
//bool isPalindrome(string s){ ll i=0,j=s.size()-1;for(i,j;i<=j;i++,j--){if(s[i]!=s[j]) return 0;} return 1;}
//bool isPowerofTwo(ll n){return (n && !(n&(n-1)));}
//int count_one(ll n){int count=0;while(n){n &= (n-1);count++;}return count;}
//string binRep(ll n){string s="";int f = 0;while(n>0){if(n%2){f=1;s+='1';}else s+='0';n/=2;}if(s.empty())return "0";else return s;}
//int ctz(ll n){return __builtin_ctzll(n);}
//int clz(ll n){return __builtin_clzll(n);}
//int bitCount(ll n){return __builtin_popcountll(n);}
 
//bool isPrime(ll n){ ///Trial Division Method
//    ll x=sqrt(n);
//    if(n==1) return 0;
//    for(ll i=2;i<=x;i++)
//        if(n%i==0) return 0;
//    return 1;
//}

//bitset<sz>is_prime;
//vi prime;
//
//void primeGen(int n){
//     for(int i=3; i<=n; i+=2)is_prime[i]=1;
//     int nn = sqrt(n)+1;
//     for(ll i=3; i<nn; i+=2){
//         if(is_prime[i]==0)continue;
//      for(int j=i*i; j<=n; j+=(i+i)){
//        is_prime[j]=0;
//      }
//     }
//     is_prime[2]=1;
//     prime.pb(2);
//     for(int i=3; i<=n; i+=2){
//        if(is_prime[i])prime.pb(i);
//     }
//
//}
//
//vector<long long>primeDivisors[sz];
//long long primeDivisorNumbers[sz];
//void findPrimeDivisors(long long n){
//  for(auto u:prime){
//    for(long long i = u; i<=n; i+=u){
//      primeDivisors[i].push_back(u);
//      primeDivisorNumbers[i]++;
//    }
//  }
//}
//
//
//vector<long long>factorization(long long n){
//  //O(sqrt(n)/ln(sqrt(n)) + log2 n)
//  vector<long long>factors;
//  for(auto u:prime){
//    if(1LL*u*u > n) break;
//    if(n%u==0){
//    //  factors.push_back(u);//for generating unique factors keep this line here
//      while(n%(u)==0){
//        //factors.push_back(u);//for generating all factors keep this line here
//        n/=(u);
//      }
//    }
//  }
//  if(n>1)factors.push_back(n);
//  return factors;
//}
//
//int NOD(long long n){
//  int res=1;
//  for(auto u:prime){
//    if(1LL*u*u > n)break;
//    if(n%u==0){
//          int count=1;
//      while(n%u==0){
//        n/=u;
//        count++;
//      }
//      res *= count;
//    }
//  }
//  if(n>1)res*=2;
//  return res;
//}

///2^n
//ll pow(ll x){
//  ll res=1;
//  if(x==0)return res;
//  for(int i=1;i<=x;i++)res*=2;
//  return res;
//}

//          R  D  L  U  uR dR dL uL
int dx[] = {0, 1, 0,-1,-1, 1, 1, -1};
int dy[] = {1, 0,-1, 0, 1, 1,-1, -1};
 
 
//--------------------------------------------------------------------------------------------------------------
//                                Code goes from here
//--------------------------------------------------------------------------------------------------------------
 
 
 
 
ll Case=0;
void solve(){
//  cout<<"Case #"<<++Case<<":"<<endl;
//  cout<<"HELLO SHADRIL!"<<endl;
  ll n,e=0,o=0;
  cin>>n;
  vi v(n);
  for(ll i=0;i<n;i++){
    cin>>v[i];
    if(v[i]%2==0)e++;
    else o++;
  }
  if((e%2==0 and o%2==0) or e==0 or o==0)cout<<0<<endl;
  else cout<<1<<endl;


  
}
int main(){
  shadril238;
//  read; 
//  write;
  int t=1; 
  cin>>t; 
  while(t--)solve();
    return 0;
}