H. GG and YY's Stone Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

GG and YY are playing a game on a pile of stones of size $$$n$$$. GG and YY play in turns. GG moves first. In each turn, the corresponding player can remove 1 or 2 stones from the pile. The player who cannot move loses. Both players want to win and get as many stones as possible. Assume GG and YY both follow the optimal strategy. Please decide the winner and answer the number of stones, $$$v$$$, that the winner gets at the end.

Input

The first line contains one integer $$$T$$$ ($$$1\le T\le 10^4$$$), indicating the number of test cases.

Each test case contains one integer $$$n$$$ ($$$1\le n\le 10^{12}$$$) in one line, indicating the number of stones.

Output

For each test case, if GG wins, output "0 $$$v$$$", otherwise output "1 $$$v$$$" (without quotes).

Example
Input
3
1
2
3
Output
0 1
0 2
1 1