GG 和 YY 正在用一堆 $n$ 个石子玩游戏。GG 和 YY 轮流操作，GG 先操作。在每一轮中，玩家可以从石子堆中移走 1 或 2 个石子。不能操作的一方输。两位玩家都想获胜，并得到尽可能多的石子。假设 GG 和 YY 都采用最优策略。请确定胜者，并回答胜者最后获得的石子数 $v$。

Input

第一行一个整数 $T$（$1\le T\le 10^4$），表示测试数据组数。

对于每组数据，每行一个整数 $n$（$1\le n\le 10^{12}$），表示石子数量。

Output

对于每组数据，如果 GG 获胜，输出 "0 $v$"，否则输出 "1 $v$''（不包含引号）。

3
1
2
3

0 1
0 2
1 1