SpongeBob recently got obsessed with his (not perfect) rectangular face and has started making rectangular $M \times 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 \times 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 ≤ 10^6$), 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×10^3$), the size of each pizza.

Output

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

Sample

Input

Output

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.