Дзідзьо й зустріч з фанатами

Limits: 2 sec., 256 MiB

Після концерту в надзвичайно дивній країні Дзідзьо вирішив роздати кілька автографів своїм палким фанатам. Він зовсім недавно думав над новим лого своєї групи (див. Примітки), тому вирішив, що його автограф буде складатися лише з нових логотипів. Щоб фанат отримав максимальне задоволення від автографа, повинні виконуватися такі дивні умови:

1. Автограф — це сітка розмірами $n$ на $m$.

2. У кожній клітинці повинно бути рівно одне лого.

3. Кількість точок, у яких закінчується лише одна стрілка логотипу, повинна бути мінімальною.

З першими двома умовами Дзідзьо розібрався одразу, а з третьою він звернувся до вас. Напишіть програму, яка допоможе йому порахувати мінімальну можливу кількість таких точок. Розмір логотипу — 1 на 1. Логотип можна повертати на 90, 180 та 270 градусів.

Input

У першому рядку задано одне ціле число $t$ — кількість фанатів.

У наступних $t$ рядках задано по два цілих числа $n_i, m_i$ — розміри автографу, який хоче $і$-ий фанат.

Output

Для кожного фаната в окремому рядку виведіть мінмальну можливу кількість точок, у яких закінчується рівно одна стрілочка.

Constraints

$1 \le t \le 100$,

35% тестів: $1 \le n_i, m_i \le 10^3$,

65% тестів: $1 \le n_i, m_i \le 10^9$.

Samples