Luntik has decided to try singing. He has a one-minute songs, b two-minute songs and c three-minute songs. He wants to distribute all songs into two concerts such that every song should be included to exactly one concert.

He wants to make the absolute difference of durations of the concerts as small as possible. The duration of the concert is the sum of durations of all songs in that concert.

Please help Luntik and find the minimal possible difference in minutes between the concerts durations.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

Each test case consists of one line containing three integers a, b, c (1 ≤ a, b, c ≤ 10^9) — the number of one-minute, two-minute and three-minute songs.

Output

For each test case print the minimal possible difference in minutes between the concerts durations.

Example

Input


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


Output


0
1
0
1

Note

In the first test case, Luntik can include a one-minute song and a two-minute song into the first concert, and a three-minute song into the second concert. Then the difference will be equal to 0.

In the second test case, Luntik can include two one-minute songs and a two-minute song and a three-minute song into the first concert, and two three-minute songs into the second concert. The duration of the first concert will be 1 + 1 + 2 + 3 = 7, the duration of the second concert will be 6. The difference of them is |7-6| = 1.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long double ld;
 
#define int             long long int
#define f               first
#define s               second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define vvi             vector<vector<int>>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
                        //                int 
#define zrobits(x)      __builtin_ctzll(x)
#define endl            "\n"
#define mod             1000000007
#define inf             1e18
#define range(a,b)      substr(a,b-a+1)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(a)          a.begin(),a.end()
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
void yesno(bool b)      {if(b) cout<<"YES\n"; else cout<<"NO\n";}

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

template <class T, class V> void logData(pair <T, V>);
template <class T> void logData(list <T>);
template <class T> void logData(forward_list <T>);
template <class T> void logData(queue <T>);
template <class T> void logData(deque <T>);
template <class T> void logData(priority_queue <T>);
template <class T> void logData(stack <T>);
template <class T> void logData(vector <T>);
template <class T> void logData(set <T>);
template <class T> void logData(unordered_set <T>);
template <class T> void logData(multiset <T>);
template <class T> void logData(unordered_multiset <T>);
template <class T, class V> void logData(map <T, V>);
template <class T, class V> void logData(unordered_map <T, V>);
template <class T, class V> void logData(multimap <T, V>);
template <class T, class V> void logData(unordered_multimap <T, V>);

#define type1 cerr<<"[ "; for(auto i:v){ logData(i); cerr<<" "; } cerr<<"]";
#define type2 cerr<<"[ "; for(T i : v){ logData(i); cerr<<" "; } cerr<<"]";
#define type3 cerr<<"["; while(!v.empty()){ logData(v.top()); v.pop(); cerr<<" "; } cerr<<"]";
#define type4 cerr<<"["; while(!v.empty()){ logData(v.front()); v.pop_front(); cerr<<" "; } cerr<<"]";
#define type5 cerr<<"["; while(!v.empty()){ logData(v.front()); v.pop(); cerr<<" "; } cerr<<"]";
#define type6 cerr<<"{"; logData(el.first); cerr<<","; logData(el.second); cerr<<"}";

#ifndef ONLINE_JUDGE
#define debug(el) cerr<<#el<<" "; logData(el); cerr<<endl;
#else 
#define debug(el);
#endif

void logData(int el){ cerr<<el; }
// void logData(unsigned int el){ cerr<<el; }
// void logData(long long el){ cerr<<el; }
// void logData(unsigned long long  el){ cerr<<el; }
void logData(float el){ cerr<<el; }
void logData(double el){ cerr<<el; }
void logData(long double el){ cerr<<el; }
void logData(char el){ cerr<<el; }
void logData(string el){ cerr<<el; }
void logData(bool el){ if(el) cout<<"true"; else cout<<"false"; }

template <class T, class V> void logData(pair <T, V> el){ type6 }
template <class T> void logData(list <T> v){ type2 }
template <class T> void logData(forward_list <T> v){ type2 }
template <class T> void logData(queue <T> v){ type5 }
template <class T> void logData(deque<T> v){ type4 }
template <class T> void logData(priority_queue<T> v){ type3 }
template <class T> void logData(stack<T> v){ type3 }
template <class T> void logData(vector<T> v){ type2 }
template <class T> void logData(set<T> v){ type2 }
template <class T> void logData(unordered_set <T> v){ type2 }
template <class T> void logData(multiset <T> v){ type2 }
template <class T> void logData(unordered_multiset <T> v){ type2 }
template <class T, class V> void logData(map <T, V> v){ type1 }
template <class T, class V> void logData(unordered_map <T, V> v){ type1 }
template <class T, class V> void logData(multimap <T, V> v){ type1 }
template <class T, class V> void logData(unordered_multimap <T, V> v){ type1 }
 
struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x)const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void init_code(){
#ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  freopen("error.txt","w",stderr);
#endif
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  using namespace std::chrono_literals;
  std::this_thread::sleep_for(-9999999999999ms);
}
 
 
/* ******************************************************************************************************************** */


void solve(){
  int a,b,c; cin>>a>>b>>c;
  a%=2; b%=2; c%=2;
  int val=a+b+c;
  if(val==0 || val==3)
    cout<<0<<endl;
  else if(val==2){
    if(b==1)
      cout<<1<<endl;
    else 
      cout<<2<<endl;
  }
  else if(val==1)
    cout<<a+b*2+c*3<<endl;
}


int32_t main(){
  init_code();
  int case_no=1;
  w(t){
    //cout<<"Case #"<<case_no++<<": ";
    solve();
  }
  return 0;
}

