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.
/**
 * Created by Himanshu
 **/

import java.util.*;
import java.io.*;
import java.math.*;

public class A1582 {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        Reader s = new Reader();
        int t = s.i();
        while (t-- > 0) {
            long a = s.l() , b = s.l() , c = s.l();
            long val = a + b*2 + c*3;
            if (val%2 == 0) out.println(0);
            else out.println(1);
        }
        out.flush();
    }

    public static void shuffle(long[] arr) {
        int n = arr.length;
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            long temp = arr[i];
            int randomPos = i + rand.nextInt(n - i);
            arr[i] = arr[randomPos];
            arr[randomPos] = temp;
        }
    }

    private static long phi(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }

    private static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b,a%b);
    }

    public static long nCr(long[] fact, long[] inv, int n, int r, long mod) {
        if (n < r)
            return 0;
        return ((fact[n] * inv[n - r]) % mod * inv[r]) % mod;
    }

    private static void factorials(long[] fact, long[] inv, long mod, int n) {
        fact[0] = 1;
        inv[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = (fact[i - 1] * i) % mod;
            inv[i] = power(fact[i], mod - 2, mod);
        }
    }

    private static long power(long a, long n, long p) {
        long result = 1;
        while (n > 0) {
            if (n % 2 == 0) {
                a = (a * a) % p;
                n /= 2;
            } else {
                result = (result * a) % p;
                n--;
            }
        }
        return result;
    }

    private static long power(long a, long n) {
        long result = 1;
        while (n > 0) {
            if (n % 2 == 0) {
                a = (a * a);
                n /= 2;
            } else {
                result = (result * a);
                n--;
            }
        }
        return result;
    }

    private static long query(long[] tree, int in, int start, int end, int l, int r) {
        if (start >= l && r >= end) return tree[in];
        if (end < l || start > r) return 0;
        int mid = (start + end) / 2;
        long x = query(tree, 2 * in, start, mid, l, r);
        long y = query(tree, 2 * in + 1, mid + 1, end, l, r);
        return x + y;
    }

    private static void update(int[] arr, long[] tree, int in, int start, int end, int idx, int val) {
        if (start == end) {
            tree[in] = val;
            arr[idx] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx > mid) update(arr, tree, 2 * in + 1, mid + 1, end, idx, val);
        else update(arr, tree, 2 * in, start, mid, idx, val);
        tree[in] = tree[2 * in] + tree[2 * in + 1];
    }

    private static void build(int[] arr, long[] tree, int in, int start, int end) {
        if (start == end) {
            tree[in] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, tree, 2 * in, start, mid);
        build(arr, tree, 2 * in + 1, mid + 1, end);
        tree[in] = (tree[2 * in + 1] + tree[2 * in]);
    }

    static class Reader {
        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar, numChars;

        public Reader() {
            this(System.in);
        }

        public Reader(InputStream is) {
            mIs = is;
        }

        public int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String s() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long l() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int i() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double d() throws IOException {
            return Double.parseDouble(s());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int[] arr(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = i();
            }
            return ret;
        }

        public long[] arrLong(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = l();
            }
            return ret;
        }
    }
//    static class pairLong implements Comparator<pairLong> {
//        long first, second;
//
//        pairLong() {
//        }
//
//        pairLong(long first, long second) {
//            this.first = first;
//            this.second = second;
//        }
//
//        @Override
//        public int compare(pairLong p1, pairLong p2) {
//            if (p1.first == p2.first) {
//                if(p1.second > p2.second) return 1;
//                else return -1;
//            }
//            if(p1.first > p2.first) return 1;
//            else return -1;
//        }
//    }
//    static class pair implements Comparator<pair> {
//        int first, second;
//
//        pair() {
//        }
//
//        pair(int first, int second) {
//            this.first = first;
//            this.second = second;
//        }
//
//        @Override
//        public int compare(pair p1, pair p2) {
//            if (p1.first == p2.first) return p1.second - p2.second;
//            return p1.first - p2.first;
//        }
//    }
}

