Coco has an infinite supply of uniquely shaped white and dark chocolates. The white chocolates are square pyramids with side lengths of $1$, and the dark chocolates are regular tetrahedra with side lengths of $1$. One day, while playing with these chocolates, Coco discovered that by stacking them properly, one can build a larger square pyramid. The specific method for building a pyramid with a base of size $R \times C$ is as follows:

1. First, fill the base with $R \times C$ white chocolates.
2. Fill the spaces between the white chocolates with dark chocolates.
3. Fill the spaces between the dark chocolates with white chocolates. After this step, the top surface becomes a flat rectangle of size $(R-1) \times (C-1)$.
4. Repeat this process until the area of the top surface becomes $0$.

The image below shows the process of filling the first layer of a $2 \times 3$ pyramid. Filling the first layer requires 8 white chocolates and 7 dark chocolates, and including the second layer requires a total of 10 white chocolates and 8 dark chocolates.

Coco wants to build a very large chocolate pyramid as a gift for Hanbyeol. Calculate how many white and dark chocolates are needed.

Input

The first line contains the number of test cases $T$. Each of the following $T$ lines contains two integers $R$ and $C$ in order.

Output

For each test case, output the number of white chocolates and dark chocolates required, separated by a space.

Examples

Input 1

2
2 3
10 10

Output 1

10 8
670 660

Note

$1 \le T \le 10^5$, $1 \le R, C \le 10^6$