B. 向左和向下
时间限制：2 秒
内存限制：512 兆字节

有一个机器人位于无限网格的单元格 $(a, b)$ 中。Misha 想把它移动到单元格 $(0, 0)$。为此，他固定了一个整数 $k$。

Misha 可以执行以下操作：选择两个整数 $dx$ 和 $dy$（均在 $0$ 到 $k$ 范围内），将机器人向左移动 $dx$ 格（$x$ 坐标减小的方向），向下移动 $dy$ 格（$y$ 坐标减小的方向）。换句话说，将机器人从 $(x, y)$ 移动到 $(x - dx, y - dy)$。

操作的成本为：

• 如果选择的 $(dx, dy)$ 是第一次使用，成本为 $1$；
• 如果该 $(dx, dy)$ 之前已经使用过，成本为 $0$。

注意，如果 $dx \neq 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)$ 所需的最小总成本。

样例
输入

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)$。
• 第四个测试用例：可以使用操作 $(4,2)$ 和 $(5,5)$。