题目描述

佩奇喜欢在饭后出门散布。

它从点$\red{(0, 0)}$开始出发, 每一步可以向周围的八个点走. 例如, 从$\red{(0, 0), }$可以走到的点是:

$\red{(1, 0)}$; $\red{(1, 1)}$; $\red{(0, 1)}$; $\red{(-1, 1)}$; $\red{(-1, 0)}$; $\red{(-1, -1)}$; $\red{(0, -1)}$; $\red{(1, -1). }$

如果一步从点 $\red{（x_i,y_i）}$走到 $\red{(x_2,y_2)，}$且 $\red{x_1≠}$$\red{x_2\&\&y_1≠}$$\red{y_2，}$那么这一步就称为对角步。

现在有 $\red{q}$个询问, 第 $\red{i}$个询问的佩奇是走正好$\red{k_i }$步到达点 $\red{(n_i,m_i)}$.

在所有可能的移动中希望能走对角步最多的一种. 佩奇希望找到最多的"对角步"数量, 或者是发现无法用刚好 $\red{k_i}$步从 $\red{(0,0)}$走到 $\red{(n_i,m_i). }$

佩奇可以访问一个点多次（包括终点）。

输出恰好用$\red{k_i }$步走到终点使用最多的对角步，如果无法恰好用 $\red{k_i}$步走到终点，则输出"$\red{-1}$"（不包括引号）

输入格式

一个整数$\red{q ，}$表示询问组数。

接下来 $\red{q}$行，每行三个整数 。

输出格式

$\red{q}$行，每行一个整数，输出最多的对角步，

如果无解则输出"$\red{-1}$"

样例

输入样例

3

2 2 3 

4 3 7 

10 1 9

输出样例

1

6

-1

提示

样例解释

第一组询问:$\red{(0,0)→}$$\red{(1,0)→}$$\red{(1,1) →}$ $\red{(2,2)}$ 第二组询问:$\red{(0,0)→}$$\red{(0,1) →}$$\red{(1,2) →}$ $\red{(0,3) →}$ $\red{(1,4) →}$$\red{(2,3) →}$ $\red{(3,2) →}$ $\red{(4,3)}$

数据范围

对于$\red{30\%}$的数据满足, $\red{1≤}$$\red{q,n_i，}$$\red{m_i，}$$\red{k_i≤}$$\red{100}$

对于$\red{100\%}$的数据满足, $\red{1≤}$$\red{n_i,m_i,k_i≤}$$\red{10^{18}, 1≤}$$\red{q≤}$$\red{<10^4}$