← 返回题目列表

Codeforces · 2199/G

G. 干扰器

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

在大小为 $$$n \times m$$$ 的场地上,有一个机器人位于点 $$$(0, 0)$$$,其任务是到达点 $$$(n, m)$$$。机器人分步移动:每一步,它可以向右移动一个单位或向上移动一个单位。换句话说,如果当前位于点 $$$(i, j)$$$,则可以一步移动到 $$$(i + 1, j)$$$ 或 $$$(i, j + 1)$$$。

你不知道机器人的具体路线,但你需要拦截它。为此,您有一个功率为 $$$r$$$ 的干扰器,您可以将其放置在场地上的任意整数点 $$$(x, y)$$$ 处($$$0 \le x \le n$$$; $$$0 \le y \le m$$$)。

该机器人被认为是 拦截 如果在其移动过程中的某个时刻,它与干扰器的距离不超过$$$r$$$。换句话说,如果机器人路径上存在一个点$$$(i, j)$$$,使得$$$\sqrt{(i - x)^2 + (j - y)^2} \le r$$$。

但有一个问题:如果你将干扰器放置得太靠近机器人路线的起点或终点,它就会被注意到,你的计划就会受到影响。因此,您需要定位干扰器,使其既不覆盖点 $$$(0, 0)$$$ 也不覆盖点 $$$(n, m)$$$(即,到它们每个点的距离必须严格大于 $$$r$$$)。

计算适合放置干扰器的点的数量。如果一个点不太靠近路线的终点,那么这个点是合适的,但同时,无论机器人走哪条路线,都会被拦截。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。以下是 $$$t$$$ 测试用例。

每个测试用例的第一行也是唯一一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$r$$$ ($$$n, m \ge 1$$$; $$$n \cdot m \le 10^9$$$; $$$1 \le r \le n + m$$$) — 场的尺寸和干扰器的功率。

输出

对于每个测试用例,输出一个整数 - 适合放置干扰器的点数。

示例

输入
复制

6
1 1 1
10 5 3
3 6 3
4 2 3
1000000000 1 2
1 1000000000 499999999

输出
复制

0
16
6
0
1999999992
4

注意

声明中说明了第二个测试用例的干扰器的一种可能放置位置。