Задача №113810. Покос
Мирко нужно купить землю, чтобы построить дом для своей семьи. Он присмотрел K участков. Для простоты будем считать, что участок представляет собой поле с N строками и M столбцами, N × M клеток в сумме.
Мирко знал, что до начала строительства участок надо поддерживать в порядке. По этой причине он приобрёл газонокосилку. Для покоса участка ему нужно проехать по каждой клетке поля хотя бы раз. Он может начать с любой клетки, смотря в одно из четырёх основных направлений (вверх, вниз, влево или вправо). Его газонокосилка может двигаться только вперёд (перемещаться в следующую клетку вдоль текущего направления) или поворачиваться на 90 градусов. К тому же, ради безопасности, Мирко может косить только на своём участке, не выходя за пределы поля.
Так как поворачивать газонокосилку непросто, Мирко хочет минимизировать количество поворотов газонокосилки. Для каждого из K участков земли ему нужно знать минимальное число поворотов для покоса. Помогите Мирко с этой задачей.
В первой строке вводится натуральное число K ( 1 ≤ K ≤ 50 000 ) — число запросов. В каждой из следующих K строк вводятся два натуральных числа N и M ( 1 ≤ N , M ≤ 10 6 ) — размеры поля для каждого запроса.
Для каждого запроса в отдельной стоке выведите минимальное число поворотов газонокосилки, которое потребуется для покоса участка.
Программы, верно работающие на тестах, в которых K = 1 , 1 ≤ N , M ≤ 500 , оцениваются в 50 баллов.
В первом примере первый участок можно покосить без поворотов, если Мирко встанет в первой клетке поля и пойдёт вперёд. Аналогичная идея относится и ко второму участку.
2 1 10 10 1
0 0
3 1 1 3 3 3 4
0 4 4
2 5 8 6 4
8 6