У Васи есть красный клетчатый прямоугольник размера \(n \times m\). Но он ему не нравится. Поэтому Вася несколько раз разрежет исходный или любой другой, получившийся в ходе разрезания, прямоугольник на две части вдоль одной из линий сетки. Он может сделать эту операцию сколько угодно раз.
В результате он получит набор прямоугольников. Прямоугольники \(1 \times 1\) запрещены.
Еще Вася умеет красить клеточки в синий цвет. Он хочет, чтобы каждый прямоугольник из набора был раскрашен так, что соседние по стороне клетки имели разные цвета.
Какое минимальное количество клеточек Васе придется покрасить?
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество клеток, которое придется покрасить Васе.
Примечание
Приведенные ниже картинки показывают, как прямоугольник может быть разрезан, и какие клетки могут быть покрашены синим после этого.
В первом наборе входных данных:
Во втором наборе входных данных:
В третьем наборе входных данных:
В четвертом наборе входных данных:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 3
2 2
2 5
3 5
|
1
2
4
5
|