Степан є менеджером кінотеатрів Supercode, і після довгої перерви кінотеатри знову відкриті для відвідувачів. Щоб компенсувати втрату доходу через Covid-19, Степан хоче відтепер максимізувати прибуток від кожного шоу та в той же час дотримуватися вказівок, встановлених урядом.

Рекомендації такі:

• Якщо двоє людей сидять в одному ряду, між ними має бути принаймні одне вільне місце.

• Якщо двоє людей сидять у різних рядах, між ними має бути хоча б один абсолютно порожній ряд. Тобто, якщо є люди, які сидять у рядах \(i\) та \(j\), де \(i \lt j\), має бути такий ряд \(k\), що \(i \lt k \lt j\) і ніхто не сидить у ряду \(k\).

Враховуючи інформацію про кількість рядів і кількість місць у кожному ряду, знайдіть максимальну кількість квитків, яку може продати Степан.

Формат вхідних даних

Перший рядок вводу міститиме одне ціле число \(T\) - кількість тестів.

Кожен тестовий приклад складається з одного рядка вхідних даних, що містить два цілі числа \(N, M\), розділені пробілами --- кількість рядів і кількість місць у кожному ряду відповідно.

Формат вихідних даних

У вихідний потік вивести, в окремих рядках для кожного тесту, відповідь на поставлене завдання

Обмеження

• \(1 \leq T \leq 100\)

• \(1 \leq N,M \leq 100\)

Приклад вхідних даних

3
1 5
3 3
4 4

Приклад вихідних даних

3
4
4