Mikhail walks on a Cartesian plane. He starts at the point (0, 0), and in one move he can go to any of eight adjacent points. For example, if Mikhail is currently at the point (0, 0), he can go to any of the following points in one move: 

  * (1, 0); 
  * (1, 1); 
  * (0, 1); 
  * (-1, 1); 
  * (-1, 0); 
  * (-1, -1); 
  * (0, -1); 
  * (1, -1). 



If Mikhail goes from the point (x1, y1) to the point (x2, y2) in one move, and x1 ≠ x2 and y1 ≠ y2, then such a move is called a diagonal move.

Mikhail has q queries. For the i-th query Mikhail's target is to go to the point (n_i, m_i) from the point (0, 0) in exactly k_i moves. Among all possible movements he want to choose one with the maximum number of diagonal moves. Your task is to find the maximum number of diagonal moves or find that it is impossible to go from the point (0, 0) to the point (n_i, m_i) in k_i moves.

Note that Mikhail can visit any point any number of times (even the destination point!).

Input

The first line of the input contains one integer q (1 ≤ q ≤ 10^4) — the number of queries.

Then q lines follow. The i-th of these q lines contains three integers n_i, m_i and k_i (1 ≤ n_i, m_i, k_i ≤ 10^{18}) — x-coordinate of the destination point of the query, y-coordinate of the destination point of the query and the number of moves in the query, correspondingly.

Output

Print q integers. The i-th integer should be equal to -1 if Mikhail cannot go from the point (0, 0) to the point (n_i, m_i) in exactly k_i moves described above. Otherwise the i-th integer should be equal to the the maximum number of diagonal moves among all possible movements.

Example

Input

3
2 2 3
4 3 7
10 1 9


Output

1
6
-1

Note

One of the possible answers to the first test case: (0, 0) → (1, 0) → (1, 1) → (2, 2).

One of the possible answers to the second test case: (0, 0) → (0, 1) → (1, 2) → (0, 3) → (1, 4) → (2, 3) → (3, 2) → (4, 3).

In the third test case Mikhail cannot reach the point (10, 1) in 9 moves.
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Random;
import java.util.StringTokenizer;

public class Main {

    String fileName = "";
    //////////////////////    SOLUTION   SOLUTION  SOLUTION    //////////////////////////////
    Long INF = Long.MAX_VALUE;
    int MODULO = 1000_000_000 + 7;
    int MAX_VALUE = 1000_1000;
    int[][] steps = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    private final static Random rnd = new Random();
    double eps = 1e-4;
    class Pair implements Comparable<Pair>{
        double val;
        int ind;

        public Pair(double val, int ind) {
            this.val = val;
            this.ind = ind;
        }

        @Override
        public int compareTo(Pair o) {
            return -Double.compare(this.val, o.val);
        }

    }


    void solve() throws IOException {

        int q = readInt();

        while (q-- > 0){
        long n = Math.abs(readLong());
        long m = Math.abs(readLong());
        long k = readLong();
        if (n>m){
            long v = n;
                n = m;
                m = v;
            }
            long res = n;
            k -= n;
            res += m-n;
            k -= m-n;
            if (k < 0){
                out.println(-1);
                continue;
            }
            if ((m-n)%2==0){
                if (k==1){
                    out.println(res-1);
                    continue;
                }
                if (k%2==0){
                    out.println(res+k);
                }else{
                    out.println(res+k-1);
                }
                continue;
            }
            if ((m-n)%2==1){
                if (k%2==1){
                    out.println(res+k - 1);
                }else{
                    out.println(res+k-2);
                }
                continue;
            }
        }

    }
    long getAns(char[] r){
        long[][][] dp = new long[4][r.length+13][2];
        if (r.length == 1){
            return r[0] - '1';
        }
        int n = r.length;
        for (int i=1; i < r[0]-'0'; ++i) dp[1][1][0]++;
        dp[1][1][1] = 1;
        for (int len=1; len<n; ++len){
            for (int prefix=0; prefix<2; ++prefix){
                for (int digit=0; digit<10; ++digit){
                    if (digit==0){
                        dp[1][len+1][prefix] = dp[1][len][prefix];
                        if (r[len] != '0') dp[1][len+1][prefix] += dp[1][len][1];
                        dp[2][len+1][prefix] = dp[2][len][prefix];
                        if (r[len] != '0') dp[2][len+1][prefix] += dp[2][len][1];
                        dp[3][len+1][prefix] = dp[3][len][prefix];
                        if (r[len] != '0') dp[3][len+1][prefix] += dp[3][len][1];
                    }else{
                        if (digit<r[len]-'0'){
                            dp[2][len+1][0] += dp[1][len][prefix];
                            dp[3][len+1][0] += dp[2][len][prefix];
                        }else if (digit==r[len]-'0') {
                            if (prefix == 1){
                                dp[2][len+1][1] += dp[1][len][prefix];
                                dp[3][len+1][1] += dp[2][len][prefix];
                            }
                            dp[2][len+1][0] += dp[1][len][prefix];
                            dp[3][len+1][0] += dp[2][len][prefix];
                        }else{
                            dp[2][len+1][0] += dp[1][len][prefix];
                            dp[3][len+1][0] += dp[2][len][prefix];
                        }
                    }
                }
            }
        }
        return dp[1][n][0] + dp[1][n][1] + dp[2][n][0] + dp[2][n][1] + dp[3][n][0] + dp[3][n][1];
    }

    long binPow(long a, long b, long m) {
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 1) {
            return ((a % m) * (binPow(a, b - 1, m) % m)) % m;
        } else {
            long c = binPow(a, b / 2, m);
            return (c * c) % m;
        }

    }
    class Point{
        long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    class Fenwik {
        int[] t;
        int n;
        Fenwik(int n){
            t = new int[n];
            this.n = n;
        }

        void inc(int r, int delta){
            for (; r < n; r = r | (r + 1)) t[r] += delta;
        }
        int getSum(int r){
            int res = 0;
            for (; r >=0; r = (r & (r + 1) ) - 1) res += t[r];
            return res;
        }
    }
    boolean isPrime(int n){
        for (int i=2; i*i<=n; ++i){
            if (n%i==0) return false;
        }
        return true;
    }
    class Edge implements Comparable<Edge>{
        int from, to, num, dist;
        Edge(int from, int to, int dist, int num){
            this.from = from;
            this.to = to;
            this.num = num;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.dist, o.dist);
        }
    }


    class Segment{
        Point p1, p2;
        public Segment(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;
        }
    }
    Point readPoint() throws IOException{
        return new Point(readInt(), readInt());
    }
    class Number implements Comparable<Number>{
        int x, cost;
        Number(int x, int cost){
            this.x = x;
            this.cost = cost;
        }

        @Override
        public int compareTo(Number o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    void readUndirectedGraph (int n, int m, int[][] graph) throws IOException{
        Edge[] edges = new Edge[m];
        int[] countEdges = new int[n];
        for (int i=0; i<m; ++i){
            int from = readInt() - 1;
            int to = readInt() - 1;
            countEdges[from]++;
            countEdges[to]++;
            edges[i] = new Edge(from, to, 0, 0);
        }
        for (int i=0; i<n; ++i) {
            graph[i] = new int[countEdges[i]];
        }
        for (int i=0; i<m; ++i){
            graph[edges[i].from][--countEdges[edges[i].from]] = edges[i].to;
            graph[edges[i].to][-- countEdges[edges[i].to]] = edges[i].from;
        }
    }
    class Vertex implements Comparable<Vertex>{
        int i, j, plus;
        Vertex(int i, int j, int plus){
            this.i = i;
            this.j = j;
            this.plus = plus;
        }

        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.plus, o.plus);
        }
    }



    ///////////////////////////////////////////////////////////////////////////////////////////

    class Dsu{
        int[] parent;
        int countSets;
        Dsu(int n){
            parent = new int[n];
            countSets = n;
            for (int i=0; i<n; ++i){
                parent[i] = i;
            }
        }
        int findSet(int a){
            if (a == parent[a]) return a;
            parent[a] = findSet(parent[a]);
            return parent[a];
        }
        void unionSets(int a, int b){
            a = findSet(a);
            b = findSet(b);
            if (a != b){
                parent[a] = b;
                countSets--;
            }
        }
    }

    class SparseTable{
        int[][] rmq;
        int[] logTable;
        int n;
        SparseTable(int[] a){
            n = a.length;
            logTable = new int[n+1];
            for(int i = 2; i <= n; ++i){
                logTable[i] = logTable[i >> 1] + 1;
            }
            rmq = new int[logTable[n] + 1][n];
            for(int i=0; i<n; ++i){
                rmq[0][i] = a[i];
            }

            for(int k=1; (1 << k) < n; ++k){
                for(int i=0; i + (1 << k) <= n; ++i){
                    int max1 = rmq[k - 1][i];
                    int max2 = rmq[k-1][i + (1 << (k-1))];
                    rmq[k][i] = Math.max(max1, max2);
                }
            }
        }

        int max(int l, int r){
            int k = logTable[r - l];
            int max1 = rmq[k][l];
            int max2 = rmq[k][r - (1 << k) + 1];
            return Math.max(max1, max2);
        }
    }
    long checkBit(long mask, int bit){
        return (mask >> bit) & 1;
    }

    static int checkBit(int mask, int bit) {
        return (mask >> bit) & 1;
    }
    boolean isLower(char c){
        return c >= 'a' && c <= 'z';
    }

    ////////////////////////////////////////////////////////////



    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }
    long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a%b);
    }
    double binPow(double a, int pow){
        if (pow == 0) return 1;
        if (pow % 2 == 1) {
            return a * binPow(a, pow - 1);
        } else {
            double c = binPow(a, pow / 2);
            return c * c;
        }
    }

    int minInt(int... values) {
        int min = Integer.MAX_VALUE;
        for (int value : values) min = Math.min(min, value);
        return min;
    }

    int maxInt(int... values) {
        int max = Integer.MIN_VALUE;
        for (int value : values) max = Math.max(max, value);
        return max;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Main().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    };

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";

    Main() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }
    byte readByte() throws NumberFormatException, IOException {
        return Byte.parseByte(readString());
    }
    int[] readIntArray (int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }

    Integer[] readIntegerArray (int n) throws NumberFormatException, IOException {
        Integer[] a = new Integer[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }

    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}