Doubled Sum of Squares

Limits: 2 sec., 256 MiB

Given $q$ pairs of integers $a_i$ and $b_i$.

For each pair find two integers $x_i$ and $y_i$ such that:

• $x_i^2 + y_i^2 = 2 \cdot (a_i^2 + b_i^2)$

• $0 \le x_i, y_i \le 2 \cdot 10^9$

It can be proven, that such numbers always exist.

«Where are Zenyk and Marichka» – you will ask. Right now they are buzy, and by the time you solve this problem, they will return.

Input

The first line of the input contains one integer $q$ – number of queries you have to answer.

Each of the following $q$ lines contains two integers $a_i$ and $b_i$.

Output

For each of $q$ queries output two integets $x_i$ and $y_i$.

Constraints

$1 \le q \le 10^5$,

$0 \le a_i, b_i \le 10^9$.

Samples