Hello Codeforces! This is my very first blog, and I wanted to share a little puzzle I created. It’s simple, but has a nice story around it. I hope you enjoy solving it!

Problem: Kids of Houses

In the distant kingdom of Alerion, two ancient families wage endless feuds: the House of Blukan and the House of Monos.

It is told that children are their only measure of wealth, power, and future wars. Both houses are known for a wicked ritual: they do not raise armies, they kidnap each other’s children.

The historians record two peculiar incidents, which strangely always occur whenever the feud begins anew:

• When the House of Blukan strikes first: They manage to capture exactly n children from Monos. After this strange event, destiny ensures that both houses suddenly hold the same number of children.

• When the House of Monos retaliates: They steal exactly the same number n of children from Blukan. Strangely, after this revenge, Monos always ends up possessing exactly twice the number of children that Blukan has left.

No one knows how or why this arithmetic fate occurs. The royal seer, however, discovered that from the value of n, the initial number of children of each house can be uniquely determined.

Task

Given the integer n, you must determine how many children House of Blukan and House of Monos originally had before the feud began.

Input

The first line contains an integer t (1 ≤ t ≤ 10⁹) — the number of test cases.

Each of the following t lines contains an integer n (1 ≤ n ≤ 10¹⁸).

Output

For each test case, output two integers: A B — the initial number of children in House of Blukan and House of Monos, respectively.