米哈伊尔在笛卡尔平面上行走。他从点 $$$(0, 0)$$$ 开始,一步即可到达八个相邻点中的任何一个。例如,如果 Mikhail 当前位于 $$$(0, 0)$$$ 点,他可以一步移动到以下任意点:
- $$$(1, 0)$$$;
- $$$(1, 1)$$$;
- $$$(0, 1)$$$;
- $$$(-1, 1)$$$;
- $$$(-1, 0)$$$;
- $$$(-1, -1)$$$;
- $$$(0, -1)$$$;
- $$$(1, -1)$$$.
如果 Mikhail 从点 $$$(x1, y1)$$$ 一次移动到点 $$$(x2, y2)$$$,并且 $$$x1 \ne x2$$$ 和 $$$y1 \ne y2$$$,那么这样的移动称为对角移动。
Mikhail 有 $$$q$$$ 查询。对于第 $$$i$$$ 查询,Mikhail 的目标是从 $$$(0, 0)$$$ 精确移动 $$$k_i$$$ 移动到 $$$(n_i, m_i)$$$ 点。在所有可能的动作中,他想选择对角线移动次数最多的一种。你的任务是找到对角线移动的最大次数,或者发现在 $$$k_i$$$ 移动中不可能从点 $$$(0, 0)$$$ 到点 $$$(n_i, m_i)$$$。
请注意,Mikhail 可以多次访问任何点(甚至是目的地点!)。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^4$$$) — 查询数。
然后是 $$$q$$$ 行。 $$$q$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$n_i$$$、$$$m_i$$$ 和 $$$k_i$$$ ($$$1 \le n_i, m_i, k_i \le 10^{18}$$$) — $$$x$$$-查询的目标点坐标,$$$y$$$-目的地坐标相应地,查询的点和查询中的移动次数。
输出
打印 $$$q$$$ 整数。如果 Mikhail 无法按照上述 $$$k_i$$$ 动作从 $$$(0, 0)$$$ 点移动到 $$$(n_i, m_i)$$$ 点,则第 $$$i$$$ 个整数应等于 -1。否则,第 $$$i$$$ 个整数应等于所有可能移动中对角线移动的最大数量。
示例
输入 #1
3 2 2 3 4 3 7 10 1 9
输出 #1
1 6 -1
注意
第一个测试用例的可能答案之一:$$$(0, 0) \to (1, 0) \to (1, 1) \to (2, 2)$$$。
第二个测试用例的可能答案之一: $$$(0, 0) \to (0, 1) \to (1, 2) \to (0, 3) \to (1, 4) \to (2, 3) \to (3, 2) \to (4, 3)$$$。
在第三个测试用例中,Mikhail 在 9 步内无法到达 $$$(10, 1)$$$ 点。