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 static java.lang.String.format;

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * https://codeforces.com/contest/1036/problem/B
 */
public class Solution1036B {

    private static ByteArrayOutputStream interceptedStream = new ByteArrayOutputStream();
    private static PrintStream systemOut = System.out;
    private static InputReader in  = new InputReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);


    public static void main(String[] args) throws IOException {

        solve();
        out.flush();
        out.close();
    }

    static void solve() {
        int q = in.nextInt();

        for (int i = 0; i < q; i++) {
            long n = in.nextLong();
            long m = in.nextLong();
            long k = in.nextLong();

            long ans = k;

            if (n % 2 != k % 2) ans--;
            if (m % 2 != k % 2) ans--;
            
            if (k < n || k < m) ans = -1;

            out.println(ans);
        }
    }

    private static void enableTestFromFile(String fileName) throws IOException {
        System.setOut(new PrintStream(interceptedStream));
        out = new PrintWriter(System.out);
        in = new InputReader(new File(fileName));
    }


    private static long[] getResultsFromInterceptedStream() {
        out.flush();
        String[] stringArray = interceptedStream.toString().split("\r\n");

        interceptedStream.reset();
        System.setOut(systemOut);
        out = new PrintWriter(System.out);

        return $.arrayStringToLong(stringArray);
    }


    /**
     * Assert method for testing.
     */
    private static class Assert {

        static void assertEquals(int actual, int expected) {
            if (actual != expected) {
                throw new RuntimeException("\n" + actual + " != "  + expected);
            }
        }

        static void assertEquals(long actual, long expected) {
            if (actual != expected) {
                throw new RuntimeException("\n" + actual + " != "  + expected);
            }
        }

        static void assertEquals(int[] actual, int[] expected) {
            if (!Arrays.equals(actual, expected)) {
                throw new RuntimeException("\n" + Arrays.toString(actual)
                    + "\n" + Arrays.toString(expected));
            }
        }

        static void assertEquals(long[] actual, long[] expected) {
            if (!Arrays.equals(actual, expected)) {
                throw new RuntimeException("\n" + Arrays.toString(actual)
                    + "\n" + Arrays.toString(expected));
            }
        }
    }


    /**
     * Class for read input.
     */
    private static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        /**
         * Read from file.
         */
        InputReader(File file) throws FileNotFoundException {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 32768);
            tokenizer = null;
        }

        /**
         * Read from stream.
         */
        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        boolean hasNext() {
            try {
                return reader.ready();
            } catch (IOException e) {
                e.printStackTrace();
                return false;
            }
        }

        String next() {

            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        long[] readArrayLong(int n) {
            long[] array = new long[n];
            for (int i = 0; i < n; i++) {

                array[i] = nextLong();
            }
            return array;
        }

        long[][] readDoubleArrayLong(int n) {
            long[][] array = new long[n][2];
            for (int i = 0; i < n; i++) {

                array[i][0] = nextLong();
                array[i][1] = nextLong();
            }
            return array;
        }
    }

    /**
     * Util class with different util methods.
     */
    private static class $ {

        static int[] ints(int... args) {
            return args;
        }

        static long[] longs(long... args) {
            return args;
        }

        static String[] strings(String... args) {
            return args;
        }

        static long[] arrayStringToLong(String[] stringArray) {
            long[] longArray = new long[stringArray.length];

            for (int i = 0; i < stringArray.length; i++) {
                longArray[i] = Long.parseLong(stringArray[i]);
            }
            return longArray;
        }

        static int[] arrayStringToInt(String[] stringArray) {
            int[] intArray = new int[stringArray.length];

            for (int i = 0; i < stringArray.length; i++) {
                intArray[i] = Integer.parseInt(stringArray[i]);
            }
            return intArray;
        }

        static long GCD(long a, long b) {
            return b == 0 ? a : GCD(b, a % b);
        }

        static boolean isPrime(long n) {
            if (n == 1) return false;

            long limit = (long) Math.sqrt(n);
            for (long i = 2; i <= limit; i++) {
                if (n % i == 0) return false;
            }
            return true;
        }

        static String[] readFile(String fileName) {
            List<String> list = new ArrayList<>();

            try (Stream<String> stream = Files.lines(Paths.get(fileName))) {
                list = stream.collect(Collectors.toList());
            } catch (IOException e) {
                e.printStackTrace();
            }
            return list.toArray(new String[0]);
        }

        static long[] readFileAsLong(String fileName) {
            return arrayStringToLong(readFile(fileName));
        }

        static int[] readFileAsInt(String fileName) {
            return arrayStringToInt(readFile(fileName));
        }
    }
}
