有天他来到一张方格地图上，整张地图可以看做一个二维坐标轴。牛牛此刻处于原点（0,0），他想要到点（x,y）去。 牛牛有强迫症，他规定自己必须恰好k步走到点(x,y)，中途可以经过任何点包括（x,y），但是第k步一定要到达（x,y）。 一步有八种走法，直线东（+1,0）南（0,-1）西（-1,0）北（0,+1），斜线东南（+1,-1）东北（+1,+1）西南（-1,-1）西北（-1,+1）。 牛牛会在能k步到达目的地的基础下尽量走斜线，你能计算出牛牛到底走了多少条斜线吗？

输入描述:

第一行一个整数T，代表数据组数。每组数据给出三个整数x，y，k。

输出描述:

对于每组数据，单独一行输出一个整数。如果牛牛可以在第k步的时候到达(x,y)，输出牛牛走的斜线数量。如果牛牛不能到达，输出-1。

备注:

对于100%的数据，1=T=1000，1=x，y，k=1000000000000000000。