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