← 返回题目列表

Codeforces · 2125/B

B. 左、下

中文机器翻译题面 查看原题

有一个机器人位于无限网格的单元格 $$$(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)$$$ 所需的最小总操作成本。

示例

输入
复制

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)$$$。