狗哥参加了一个游戏，游戏要求狗哥从（0,0）出发，前往（n,m），游戏要一共k步，每一步有8方向可以选择。 （1,0) (1,1) (0,1) (−1,1) (−1,0) (−1,−1) (0,−1) (1,−1) 游戏规则要求狗哥更多去斜着走，斜着走的步数就是最终奖励的个数 现在狗哥想让你帮帮忙，计算出他能获得的最多的奖励

Input 第一行输入一个整数q(1<=q<=10^4) 接下来q行，每行包括3个整数ni,mi,ki(1<=ni,mi,ki<=10^18)

Output 每个样例输出一行 如果狗哥无法到达（n,m）则输出-1 如果能则输出狗哥的奖励数

Example Input 3 2 2 3 4 3 7 10 1 9 Output 1 6 -1 Note 第一个样例一种可能的答案: (0, 0) -> (1, 0) -> (1, 1) -> (2, 2).

第二个样例一种可能的答案: (0, 0) -> (0, 1) -> (1, 2) -> (0, 3) -> (1, 4) -> (2, 3) -> (3, 2) -> (4, 3).

第三个样例中，狗哥不能在9步中走到 (10, 1) .