A. Смена направления
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана сетка, состоящая из $$$n$$$ строк и $$$m$$$ столбцов. Строки и столбцы пронумерованы от $$$1$$$ до $$$n$$$ и от $$$1$$$ до $$$m$$$ соответственно. Пересечение $$$a$$$-й строки и $$$b$$$-го столбца обозначим за $$$(a, b)$$$.

Изначально вы находитесь в верхнем левом углу $$$(1, 1)$$$. Ваша цель — добраться до нижнего правого угла $$$(n, m)$$$

Из клетки $$$(a, b)$$$ вы можете двигаться в четырех направлениях: вверх в клетку $$$(a-1, b)$$$, вниз в $$$(a+1, b)$$$, влево в $$$(a, b-1)$$$ или вправо в $$$(a, b+1)$$$

Вам запрещается двигаться в одном направлении дважды подряд, вы не можете покидать пределы сетки. За какое минимальное количество шагов можно добраться до $$$(n, m)$$$?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — размер сетки.

Выходные данные

Для каждого набора входных данных выведите одно целое число: $$$-1$$$, если нельзя добраться до $$$(n, m)$$$ при заданных ограничениях, в ином случае — минимальное количество шагов.

Пример
Входные данные
6
1 1
2 1
1 3
4 2
4 6
10 5
Выходные данные
0
1
-1
6
10
17
Примечание

$$$1$$$-й набор входных данных: $$$n=1$$$, $$$m=1$$$, изначально вы находитесь в $$$(1, 1)$$$, поэтому $$$0$$$ шагов необходимо, чтобы добраться до $$$(n, m) = (1, 1)$$$ .

$$$2$$$-й набор: нужно сделать один шаг вниз, чтобы достичь $$$(2, 1)$$$.

$$$3$$$-й набор: невозможно достичь $$$(1, 3)$$$, не сделав подряд два шага вправо или не покидая пределы сетки.

$$$4$$$-й набор: оптимальная последовательность шагов выглядит например так: $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (4, 2)$$$. Можно доказать, что это оптимальное решение. Таким образом, ответ равен $$$6$$$.