Василько грає цікаву гру. На початку є таблиця з \(N\) рядків та \(M\) стовбців. Всі клітинки цієї таблиці незафарбовані. На рахунку гравця 0 балів. На черговому ході гравець вибирає деяку незафарбовану клітинку, зафарбовує її і добавляє до свого рахунку число сусідніх по сторонах зафарбованих клітинок.

Гра закінчується коли всі клітинки будуть зафарбованими.

Василько старається отримати найбільший результат. Допоможіть йому взнати, який максимальний результат він зможе отримати.

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

Перший рядок вхідного потоку містить ціле число \(Т\) \((1 ≤ T ≤ 100)\) — кількість тестів.

Єдиний рядок кожного тесту містить цілі числа \(N, M\) \((1 ≤ N, M ≤ 1000)\).

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

Для кожного тесту виведіть максимальний результат гри.

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

1
2 2

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

4