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>
using namespace std;
const long long int maxn = 1e5 + 6;
const long long int MOD = 1e9 + 7;
vector<int> prim(1000005, 1);
int fact[maxn];
long long int binomialCoeff(long long int n, long long int k) {
  long long int res = 1;
  if (k > n - k) k = n - k;
  for (long long int i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
bool isVowel(char ch) {
  if (ch == 'a' || ch == 'i' || ch == 'e' || ch == 'u' || ch == 'o') {
    return true;
  }
  return false;
}
long long int power(long long int x, long long int i, long long int mod) {
  long long int ans = 1;
  while (i > 0) {
    if (i & 1) ans = (ans * x) % mod;
    i >>= 1;
    x = (x * x) % mod;
  }
  return ans;
}
long long int modInverse(long long int x, long long int mod) {
  return power(x, mod - 2, mod);
}
int nCr(int n, int r) {
  if (n < r) {
    return 0;
  }
  return (((fact[n] * modInverse(fact[n - r], MOD)) % MOD) *
          modInverse(fact[r], MOD)) %
         MOD;
}
long long int power(int x, unsigned int y) {
  long long int temp;
  if (y == 0) return 1;
  temp = power(x, y / 2);
  if (y % 2 == 0)
    return temp * temp;
  else
    return x * temp * temp;
}
void erath(int n) {
  prim[1] = 0;
  prim[0] = 0;
  prim[2] = 1;
  for (int i = 2; i * i <= n; i++) {
    if (prim[i]) {
      for (int j = i * i; j <= n; j += i) {
        prim[j] = 0;
      }
    }
  }
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int lcm(long long int a, long long int b) {
  return (a / gcd(a, b)) * b;
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second < b.second);
}
long long int n, m, k;
int getmid(int l, int r) { return (l + (r - l) / 2); }
struct segtree {
  int siz;
  vector<pair<long long int, long long int> > sums;
  void init(int n) {
    siz = 1;
    while (siz < n) siz *= 2;
    sums.assign(2 * siz, {LONG_MAX, 0});
  }
  void set(int i, int v, int cur, int l, int r) {
    if (r - l == 1) {
      sums[cur].first = v;
      sums[cur].second = 1;
      return;
    }
    int m = getmid(l, r);
    if (i < m) {
      set(i, v, 2 * cur + 1, l, m);
    } else
      set(i, v, 2 * cur + 2, m, r);
    sums[cur].first = min(sums[2 * cur + 1].first, sums[2 * cur + 2].first);
    if (sums[2 * cur + 1].first == sums[cur].first &&
        sums[2 * cur + 2].first == sums[cur].first) {
      sums[cur].second = sums[cur * 2 + 1].second + sums[cur * 2 + 2].second;
    } else if (sums[2 * cur + 1].first == sums[cur].first) {
      sums[cur].second = sums[cur * 2 + 1].second;
    } else {
      sums[cur].second = sums[cur * 2 + 2].second;
    }
  }
  void set(int i, int v) { set(i, v, 0, 0, siz); }
  pair<long long int, long long int> sum(int l, int r, int cur, int lx,
                                         int rx) {
    if (lx >= r || l >= rx) return {LONG_MAX, 0};
    if (lx >= l && rx <= r) return {sums[cur].first, sums[cur].second};
    int mid = getmid(lx, rx);
    pair<long long int, long long int> s1 = sum(l, r, 2 * cur + 1, lx, mid),
                                       s2 = sum(l, r, 2 * cur + 2, mid, rx);
    if (s1.first < s2.first) {
      return s1;
    } else if (s1.first > s2.first)
      return s2;
    else
      return {s1.first, s1.second + s2.second};
  }
  pair<long long int, long long int> sum(int l, int r) {
    return sum(l, r, 0, 0, siz);
  }
};
int nCrModp(int n, int r, int p) {
  if (r > n - r) r = n - r;
  int C[r + 1];
  memset(C, 0, sizeof(C));
  C[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = min(i, r); j > 0; j--) C[j] = (C[j] + C[j - 1]) % p;
  }
  return C[r];
}
void ans(int top) {
  cin >> n >> m >> k;
  long long int mx = max(n, k), mn = min(m, n);
  if ((mn + (mx - mn)) > k) {
    cout << -1 << endl;
    return;
  }
  if (m == n) {
    cout << (mn - 1 + k - (3)) << endl;
    return;
  }
  cout << (mn + k - (mx - mn)) << endl;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1, co = 1;
  cin >> t;
  while (t--) {
    ans(co);
    co++;
  }
  return 0;
}
