Description

对于一个横向长为 $n$，纵向长为 $m$ 的台球桌。

从左下角向右 $x$ 个单位长度的位置发球，角度为 $45$ 度，假设球的动力无限，直到进洞才停止（台球桌的四个角都有洞）。

设左上方的洞为 $1$,左下方的洞为 $3$,右上方的洞为 $2$,右下方的洞为 $4$。

求最后球会进哪个编号的洞。

Format

Input

第一行一个数字 $T$。

接下来 $T$ 行，每行两个正整数 $n,m,x$。

Output

一行一个整数，即答案。

Samples

2
3 2 2
3 2 0

3
1

Limitation

对于第一组数据，设左下角坐标为 $(0,0)$。

路线为：$(2,0)\to(3,1)\to(2,2)\to(0,0)$

$T\leqslant10^5$

$1\le m,x\lt n\le2 \times 10^9$

保证 $n$ 是质数。