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

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

Input (stdin) сopy	Output (stdout) сopy
3 1 1 1 2 4 3	3 2 0