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.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
namespace fastinput {
template <class T = int>
inline T readInt();
inline long double readDouble();
inline int readUInt();
inline int readChar();
inline void readWord(char *s);
inline bool readLine(char *s);
inline bool isEof();
inline int peekChar();
inline bool seekEof();
template <class T>
inline void writeInt(T x);
template <class T>
inline void writeUInt(T x, int len = -1);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void writeDouble(long double x, int len = 0);
inline void flush();
static const int buf_size = 4096;
static char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
inline bool isEof() {
  if (buf_pos == buf_len) {
    buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
    if (buf_pos == buf_len) return 1;
  }
  return 0;
}
inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; }
inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; }
inline bool seekEof() {
  int c;
  while ((c = peekChar()) != -1 && c <= 32) buf_pos++;
  return c == -1;
}
inline int readChar() {
  int c = getChar();
  while (c != -1 && c <= 32) c = getChar();
  return c;
}
inline int readUInt() {
  int c = readChar(), x = 0;
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return x;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
inline long double readDouble() {
  int s = 1, c = readChar();
  long double x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  if (c == '.') {
    c = getChar();
    long double coef = 1;
    while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 0.1), c = getChar();
  }
  return s == 1 ? x : -x;
}
inline void readWord(char *s) {
  int c = readChar();
  while (c > 32) *s++ = (char)c, c = getChar();
  *s = 0;
}
inline bool readLine(char *s) {
  int c = getChar();
  while (c != '\n' && c != -1) *s++ = (char)c, c = getChar();
  *s = 0;
  return c != -1;
}
static int write_buf_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_buf_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
  write_buf[write_buf_pos++] = (char)x;
}
inline void flush() {
  if (write_buf_pos)
    fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
}
template <class T>
inline void writeInt(T x) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
}
template <class T>
inline void writeUInt(T x, int output_len) {
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = (char)('0' + (char)(x % 10)), x /= 10;
  while (n < output_len) s[n++] = '0';
  while (n--) writeChar(s[n]);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
inline void writeDouble(long double x, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  int t = (int)x;
  writeUInt(t), x -= t;
  writeChar('.');
  for (int i = output_len - 1; i > 0; i--) {
    x *= 10;
    t = std::min(9, (int)x);
    writeChar('0' + t), x -= t;
  }
  x *= 10;
  t = std::min(9, (int)(x + 0.5));
  writeChar('0' + t);
}
}  // namespace fastinput
using namespace fastinput;
using namespace std;
const int MAX_MEM = 2e8;
int mpos = 0;
char mem[MAX_MEM];
inline void *operator new(size_t n) {
  mpos += n;
  return (void *)(mem + mpos - n);
}
inline void operator delete(void *) noexcept {}
const int N = 2e5 + 10;
long long a[N];
long long dp[N];
const long long INF = 1LL << 60;
long long query(long long x, long long y, long long k) {
  x = abs(x);
  y = abs(y);
  if (x < y) swap(x, y);
  if (x > k) return -1;
  if (y != 0) return query(x - y, 0, k - y) + y;
  if (x > 1) {
    long long steps = x / 2;
    return query(x % 2, 0, k - steps * 2) + steps * 2;
  } else {
    if (x == 1) {
      return k - 1;
    } else if (x == 0) {
      if (k == 1) return -1;
      if (k % 2 == 0) {
        return k / 2;
      } else {
        return query(0, 0, k - 3) + 1;
      }
    }
  }
}
int main() {
  int q = readInt();
  for (int i = 0; i < q; ++i) {
    long long x = readInt<long long>(), y = readInt<long long>(),
              k = readInt<long long>();
    cout << query(x, y, k) << endl;
  }
  return 0;
}
