28898번 - Стаканчики 다국어

문제

Генри Браун хочет провести приятный вечер за чтением газеты. К его несчастью, Паддингтон нашел огромную коробку пластиковых стаканчиков.

Мишка знает, что из стаканчиков можно строить красивые пирамиды, каждый стакан в которых, не считая основания, ставится на края четырех других. Таким образом, если в основании пирамиды находится прямоугольник, состоящий из $N \times M$ стаканов, то следующий уровень будет состоять из $(N-1) \times (M-1)$ стаканов, следующий из $(N-2) \times (M-2),ドル и так далее$\dots$ Уровни продолжаются до тех пор, пока можно поставить стаканчик на края четырех других стаканчиков из предыдущего уровня.

Паддингтон никак не может определиться, какое основание будет у пирамиды, которую он построит, и сколько на нее уйдет стаканчиков. Паддингтону сложно посчитать такие числа, тем более, что они могут быть большими, поэтому он донимает мистера Брауна. Помогите Генри Брауну ответить на все вопросы настырного медвежонка.

입력

В первой строке задано одно натуральное число $t$ --- число оснований, интересующих Паддингтона (1ドル \le t \le 10^5$).

В следующих $t$ строках заданы пары чисел $N_i,ドル $M_i$ --- размеры оснований (1ドル \le N_i, M_i \le 10^9$).

출력

Для каждого основания в отдельной строке выведите число стаканчиков, которые потребуются, чтобы построить пирамиду из стаканчиков с соответствующим основанием.

제한

힌트