| Kotlin Heroes: Episode 14 |
|---|
| Закончено |
На поле $$$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$$$) — размеры поля и мощность глушилки.
Для каждого набора входных данных выведите единственное число — количество точек, подходящих для размещения в них глушилки.
61 1 110 5 33 6 34 2 31000000000 1 21 1000000000 499999999
0166019999999924
Одно из возможных расположений глушилки для второго набора входных данных изображено в условии.
| Название |
|---|


