Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Pizza From SpongeBob

By mainstring · Limits 3s, 1.0 GB

SpongeBob recently got obsessed with his (not perfect) rectangular face and has started making rectangular M x N grid like pizzas for his customers. Yes, he sells pizzas nowadays. If anyone can tell him how many unique rectangles can be found in this M x N grid (rectangle’s corners have to be any of the integer points within the grid), then SpongeBob will serve them that pizza for free!

Now you all know this brainless friend of SpongeBob, Patrick, who just forgot where he keeps his money, wants to have free pizzas from Sponge. Help Patrick to solve this challenge.

Input

You will be given C (1 ≤ C ≤ 106), the number of pizzas Patrick wants to have followed by C lines.

Each line will contain two numbers: M and N (1 ≤ M, N ≤ 3×103), the size of each pizza.

Output

Print one line for each pizza containing the answer of the challange.

Samples

InputOutput
3
2 2
3 3
10 20
10
44
18841

Explanation for the first case:

There are 9 orthogonal and 1 diagonal (red colored) rectangles.

Discussion
Submit

Login to submit