A new year has started, and I want to make a clear commitment to myself. Last year I wasted time on useless things and lacked consistency, but this year I want to change that. I want to dedicate myself fully to competitive programming, practice daily, participate seriously in contests, and focus on improving my thinking and problem-solving skills. My main goal for this year is to reach Candidate Master on Codeforces. I know it won’t be easy, but with discipline, consistency, and honest effort, I believe it’s achievable. This blog is a reminder to myself to stay focused and not give up.

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.