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.
import java.net.Inet4Address;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class practiceb{

    static FastScanner sc;
    static int ans;
    static long[] arr,arr1;
    static char[][] board;
    static long mul,mul1;
    static int[] spf;
    static char[] ch;
    static int n,q,m;
    static long k,a,x,c;
    static StringBuilder sb,sb1;
    static long b,sum;
    static Map<Integer,List<Node>> map;
    static Map<Long,List<Integer>> map2;
    static Map<Long,List<Integer>> map3;
    static Map<Integer,Integer> shortest;
    static Map<Integer,Integer> map1,in;
    static List<Long> list,list1;
    static int[] count;
    static boolean[] vis;
    static boolean flag;
    static long total,xor1;

    // static class Node{
    //     long dist;
    //     Set<Integer> set;
    //     Node(){
    //         this.set = new HashSet<>();
    //     }
    //     Node(int f){
    //         this.dist = f;
    //         this.set = new HashSet<>();
    //     }
    // }

    // public static class Lca {

    //     int[] depth;
    //     int[] dfs_order;
    //     int cnt;
    //     int[] first;
    //     int[] minPos;
    //     int n;

    //     void dfs(List<Integer>[] tree, int u, int d) {
    //         depth[u] = d;
    //         dfs_order[cnt++] = u;
    //         for (int v : tree[u])
    //             if (depth[v] == -1) {
    //                 dfs(tree, v, d + 1);
    //                 dfs_order[cnt++] = u;
    //             }
    //     }

    //     void buildTree(int node, int left, int right) {
    //         if (left == right) {
    //             minPos[node] = dfs_order[left];
    //             return;
    //         }
    //         int mid = (left + right) >> 1;
    //         buildTree(2 * node + 1, left, mid);
    //         buildTree(2 * node + 2, mid + 1, right);
    //         minPos[node] = depth[minPos[2 * node + 1]] < depth[minPos[2 * node + 2]] ? minPos[2 * node + 1] : minPos[2 * node + 2];
    //     }

    //     public Lca(List<Integer>[] tree, int root) {
    //         int nodes = tree.length;
    //         depth = new int[nodes];
    //         Arrays.fill(depth, -1);

    //         n = 2 * nodes - 1;
    //         dfs_order = new int[n];
    //         cnt = 0;
    //         dfs(tree, root, 0);

    //         minPos = new int[4 * n];
    //         buildTree(0, 0, n - 1);

    //         first = new int[nodes];
    //         Arrays.fill(first, -1);
    //         for (int i = 0; i < dfs_order.length; i++)
    //             if (first[dfs_order[i]] == -1)
    //                 first[dfs_order[i]] = i;
    //     }

    //     public int lca(int a, int b) {
    //         return minPos(Math.min(first[a], first[b]), Math.max(first[a], first[b]), 0, 0, n - 1);
    //     }

    //     int minPos(int a, int b, int node, int left, int right) {
    //         if (a == left && right == b)
    //             return minPos[node];
    //         int mid = (left + right) >> 1;
    //         if (a <= mid && b > mid) {
    //             int p1 = minPos(a, Math.min(b, mid), 2 * node + 1, left, mid);
    //             int p2 = minPos(Math.max(a, mid + 1), b, 2 * node + 2, mid + 1, right);
    //             return depth[p1] < depth[p2] ? p1 : p2;
    //         } else if (a <= mid) {
    //             return minPos(a, Math.min(b, mid), 2 * node + 1, left, mid);
    //         } else if (b > mid) {
    //             return minPos(Math.max(a, mid + 1), b, 2 * node + 2, mid + 1, right);
    //         } else {
    //             throw new RuntimeException();
    //         }
    //     }
    // }

    // private static long dfs(int v, int parent,long ht) {

    //     List<Integer> list = map.get(v);
    //     hyt[v] = ht;

    //     if(list.size() == 1){
    //         if(!map3.containsKey(ht))
    //             map3.put(ht,new ArrayList<>());

    //         map3.get(ht).add(v);
    //         return ht;

    //     }

    //     long maxl = -1;
    //     for(Integer i : list){
    //         if(i == parent)
    //             continue;
    //         maxl = Math.max(maxl,dfs(i,v,ht+1));
    //     }

    //     return maxl;

    // }
    // public static int N = 100005;

    // long a[N];
    // long sfx[N];
    // long pfx[N];

//    public static boolean f(int width){
//
//        // long[] a = new long[n];
//        long[] sfx = new long[n];
//        long[] pfx = new long[n];

//        for (int j = 0; j < n; j++){
//            if (j % width == 0){
//                pfx[j] = a[j];
//            }
//            else pfx[j] = gcd(pfx[j - 1], a[j]);
//        }
//        for (int j = n - 2; j >= 0; j--){
//            if (j % width == width - 1){
//                sfx[j] = a[j];
//            }
//            else sfx[j] = gcd(sfx[j + 1], a[j]);
//        }
//
//        for(int j = 0; j < n - width + 1 ; j++){
//            if (gcd(sfx[j], pfx[j + width - 1]) >= k) return true;
//            if (((j % width) == width - 1) && pfx[j] >= k){
//                return true;
//            }
//        }
//        return false;
//    }

    public static class Node {
        int v;
        int wt;
        Node(int v,int wt) {
            this.v = v;
            this.wt = wt;
        }
    }

    public static void solve() {

        long div1 = a%2;
        long div2 = b%2;
        long div3 = c%2;

        if(div1 + div2 + div3 == 3) {
            sb.append("0\n");
        }
        else if(div1 + div2 == 2) {
            sb.append("1\n");
        }
        else if(div3 + div2 == 2) {
            sb.append("1\n");
        }
        else if(div1 + div3 == 2) {
            if(a >= 3)
                sb.append("0\n");
            else
                sb.append("2\n");
        }
        else {
            if(div1 != 0)
                sb.append("1\n");
            else if(div2 != 0) {
                if (a >= 2)
                    sb.append("0\n");
                else
                    sb.append("2\n");
            }
            else {
                if(a >=2 || b >= 2)
                    sb.append("1\n");
                else
                    sb.append("3\n");
            }
        }

    }

    public static void main(String[] args) {

        sc = new FastScanner();
        // Scanner sc = new Scanner(System.in);
        // SpecialSieve(5000000+5);
//        long num = 1;
//        list = new ArrayList<>();
//        for(int i = 0 ; i <= 60 ; i++) {
//            list.add(num);
//            num *= 2;
//        }
        int t = sc.nextInt();
//        fact(200000+1);
        sb = new StringBuilder();
//        int t = 1;
        while(t > 0){

            a = sc.nextLong();
            b = sc.nextLong();
            c = sc.nextLong();
//            n = sc.nextInt();
            // x = sc.nextLong();
//             m = sc.nextInt();
//            k = sc.nextInt();
            // mat = new int[2][m];

            // for(int i = 0 ; i < 2 ; i++)
            //     for(int j = 0 ; j < m ; j++)
            //         mat[i][j] = sc.nextLong();

            // for(int i = 1 ; i <= 15 ; i++){
            //     m = i;
            //     solve();
            // // }
            // board = new char[3][3];
            // for(int i = 0 ; i < 3 ; i++){
            //     String s = sc.next();
            //     for(int j = 0 ; j < 3 ; j++){
            //         board[i][j] = s.charAt(j);
            //     }
            // }
            // x = sc.nextInt();
//             ch = sc.next().toCharArray();
            // q = sc.nextInt();
//             ch = sc.next().toCharArray();
//            arr = new long[n];
//            for(int i = 0 ; i < n ; i++)
//                arr[i] = sc.nextLong();
//
//            arr1 = new long[m];
//            for(int i = 0 ; i < m ; i++)
//                arr1[i] = sc.nextLong();
//
//            a = new long[n-1];
//            for(int i = 1 ; i < n ; i++)
//                a[i-1] = Math.abs(arr[i] - arr[i-1]);
//
//            n -= 1;

            solve();
            t -= 1;
        }
        System.out.print(sb);

    }

    // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
    // worst case since it uses a version of quicksort. Although this would never
    // actually show up in the real world, in codeforces, people can hack, so
    // this is needed.
    static void ruffleSort(long[] a) {
        //ruffle
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n);long temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }

        //then sort
        Arrays.sort(a);
    }
    public static long gcd(long a, long b)
    {
        if (b == 0)
            return a;

        return gcd(b, a % b);

    }
    public static int log(double n,double base){

        if(n == 0 || n == 1)
            return 0;

        if(n == base)
            return 1;

        double num = Math.log(n);
        double den = Math.log(base);

        if(den == 0)
            return 0;

        return (int)(num/den);
    }
    public static long mod(long x, long mod)
    {
        long result = x % mod;
        if (result < 0)
        {
            result += mod;
        }
        return result;
    }

    // Use this to input code since it is faster than a Scanner
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}
