Chocolate Pyramid

Time limit1sMemory limit1024 MB

Summary

Given an R x C base, count the white and dark chocolates needed to build the full pyramid, layer by layer, until the top face is empty.

Level: Medium5 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Coco has an unlimited number of white chocolates and dark chocolates with unusual shapes. A white chocolate is a square pyramid where every edge has length 1, and a dark chocolate is a regular tetrahedron where every edge has length 1. One day, while playing with these chocolates, Coco found that they can be stacked to build a larger square pyramid. The method for stacking a pyramid whose base is an $R \times C$ rectangle is as follows.

First, fill the base with $R \times C$ white chocolates.
Fill the gaps between the white chocolates with dark chocolates.
Fill the spaces between the dark chocolates with white chocolates again. After this step, the top face is a flat $(R-1) \times (C-1)$ rectangle.
Repeat until the area of the top face is 0.

The figure below shows how the first layer of a $2 \times 3$ pyramid is filled. Filling the first layer requires 8 white chocolates and 7 dark chocolates. Including the second layer, the totals are 10 white chocolates and 8 dark chocolates.

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

Input

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

Output

For each test case, print the number of white chocolates and the number of dark chocolates needed, in that order, on one line.

Constraints

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

Examples1

Example 1
Input
```
2
2 3
10 10
```
Expected output
```
10 8
670 660
```