题目描述

有一个机器人位于一片无限网格的格子 $(a,b)$ 处，Misha 想要把它移动到格子 $(0,0)$。为了完成这一点，他确定了一个整数 $k$。

Misha 可以执行以下操作：选择两个整数 $dx,dy$（在 $0$ 到 $k$ 之间），将机器人左移 $dx$ 个格子（向减少 $x$ 坐标的方向）并下移 $dy$ 个格子（向减少 $y$ 坐标的方向）。或者说，将机器人从 $(x,y)$ 移动到 $(x-dx,y-dy)$。

此操作的花费是：

• $1$，如果选择的数对 $(dx,dy)$ 是第一次被选用；
• $0$，如果数对 $(dx,dy)$ 在之前被选用过。

注意如果 $dx\ne dy$，数对 $(dx,dy)$ 和 $(dy,dx)$ 被视作不同的数对。

帮助 Misha 用最小的总代价把机器人移动到 $(0,0)$。注意你不需要最小化操作次数。

输入格式

多组数据。第一行一个整数 $t(1\le t\le 10^4)$，表示数据组数。

对于每组数据，一行三个整数 $a,b,k(1\le a,b,k\le 10^{18})$。

输出格式

对于每组数据，输出一行一个整数，表示把机器人移动到格子 $(0,0)$ 需要的最小总花费。

说明/提示

样例解释

对于第一组数据，可以执行一次操作 $(3,5)$。机器人立即移动到 $(0,0)$，总花费为 $1$。

对于第二组数据，可以执行操作 $(1,1),(0,1),(1,1)$。第一次操作后机器人位于 $(1,2)$，第二次后位于 $(1,1)$，第三次后位于 $(0,0)$。第一次和第二次操作的花费都是 $1$，第三次操作的花费为 $0$，因为 $(1,1)$ 在第一次操作时已被选用过。

对于第三组数据，可以连续使用三次操作 $(4,6)$。

对于第四组数据，可以使用操作 $(4,2),(5,5)$。

样例

4
3 5 15
2 3 1
12 18 8
9 7 5

1
2
1
2