컵 피라미드

헨리 브라운은 신문을 읽으며 즐거운 저녁을 보내고 싶어 한다. 안타깝게도 패딩턴이 거대한 플라스틱 컵 상자를 찾아냈다. 곰은 컵을 쌓아 예쁜 피라미드를 만들 수 있다는 것을 안다. 밑면을 제외한 각 컵은 아래에 있는 컵 네 개의 가장자리 위에 놓인다. 밑면이 $N \times M$ 개의 컵으로 이루어진 직사각형이면, 다음 층은 $(N-1) \times (M-1)$ 개, 그다음 층은 $(N-2) \times (M-2)$ 개로 이루어지고, 이런 식으로 계속된다. 층은 이전 층의 컵 네 개 위에 컵을 올릴 수 있는 동안 계속 쌓인다. 패딩턴은 피라미드의 밑면을 어떻게 정할지, 그리고 컵이 몇 개 필요할지 정하지 못하고 있다. 이 수는 커질 수 있어 세기 어렵고, 그래서 그는 브라운 씨를 계속 귀찮게 한다. 헨리 브라운이 곰의 질문에 모두 답하도록 도와라.

첫 줄에 패딩턴이 궁금해하는 밑면의 개수 $t$가 자연수로 주어진다 ($1 \le t \le 10^5$). 다음 $t$개 줄에는 밑면의 크기 $N_i$, $M_i$가 주어진다 ($1 \le N_i, M_i \le 10^9$).

각 밑면마다 한 줄에, 그 밑면으로 피라미드를 쌓는 데 필요한 컵의 개수를 출력한다.