Известно, что блохи в Берляндии могут прыгать только по вертикали и горизонтали, причем прыгают они всегда ровно на s сантиметров. В центре некоторой клетки прямоугольной клетчатой доски n × m сантиметров (размер одной клетки — 1 × 1 сантиметр) оказалась блоха. Она может прыгать по доске сколько угодно, может даже посещать одну и ту же клетку несколько раз. Единственное ограничение — блоха не может выпрыгивать за пределы доски.
Блоха может посчитать количество клеток, до которых она может добраться из начальной позиции (x, y). Назовем это количество dx, y. Ваша задача — найти количество таких начальных позиций блохи (x, y), для которых dx, y максимально.
Выходные данные
Выведите одно целое число — количество начальных позиций блохи, для которых количество клеток, до которых блоха может добраться из этой начальной позиции, максимально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 1000000
|
6
|
|
2
|
3 3 2
|
4
|