问题描述

在一个无限网格的 $(a,b)$ 单元中有一个机器人。米沙想要将它移动到 $(0,0)$ 单元。为此，他设定了一个整数 $k$ 。

米沙可以执行以下操作：选择两个整数 $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)$ 会被视为不同的一对。

帮助米莎以最小的总成本将机器人带到 $(0,0)$ 小区。请注意，您不必尽量减少操作次数。

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例数。

每个测试用例的唯一一行包含三个整数 $a, b$ 和 $k$ ( $1 \le a, b, k \le 10^{18}$ )。

输出格式

对于每个测试案例，输出一个整数 - 将机器人移动到 $(0,0)$ 单元所需的最小总操作成本。

样例输入

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

样例输出

1
2
1
2

说明

在第一个测试案例中，可以执行一次 $(3,5)$ 操作。机器人将立即前往 $(0,0)$ ，操作成本为 $1$ 。

在第二个测试案例中，操作可以执行 $(1,1)$ 、 $(0,1)$ 和 $(1,1)$ 操作。第一次操作后，机器人将位于 $(1,2)$ 单元；第二次操作后，机器人将位于 $(1,1)$ 单元；第三次操作后，机器人将位于 $(0,0)$ 单元。第一次和第二次操作的成本为 $1$ ，而第三次操作的成本为 $0$ ，因为在第一次操作中已经使用了一对 $(1,1)$ 。

在第三个测试案例中， $(4,6)$ 可以连续选择三次。