小q的数列
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题转译自 [南昌大学航天杯第二届程序设计竞赛校赛网络同步赛] 小q的数列 。
\hspace{15pt}小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：
f(x) = \begin{cases} <br /> 0 & x=0 \\<br /> 1 & x=1 \\<br /> f(\left\lfloor \frac{x}{2} \right\rfloor)+f(x\bmod2) & x \geq 2<br />\end{cases}
\hspace{15pt}现在，他想考考你，问：给你一个 n，代表数列的第 n 项，你能不能马上说出 f(n) 的值是多少，以及 f(n) 所代表的值第一次出现在数列的哪一项中？（即，若这个数列里某几项 f(n_1) = f(n_2) = \cdots = f(n_k) 的值是相等的，则输出最小的那个 n 的值 \min\left(n_1, n_2, \cdots, n_k\right) ）。

\hspace{15pt}在本题中，\left\lfloor {x} \right\rfloor表示向下取整，x \bmod y 表示 x 除以 y 的余数。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 5 \times 10^5\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}在一行上输入一个整数 n\left(1\leqq n\leqq 10^{18}\right) ，代表数列的第 n 项。

输出描述:

\hspace{15pt}对于每一组测试数据，在单独的一行上输出两个整数，分别代表 f(n) 的值和 f(n) 所代表的值第一次出现在数列的哪一项中。
示例1

输入

复制 
6
0
1
2
3
4
5

输出

复制 
0 0
1 1
1 1
2 3
1 1
2 3

说明

\hspace{15pt}这个数列的前六项为：
\hspace{23pt}\bullet\,f(0) = 0 ；
\hspace{23pt}\bullet\,f(1) = 1 ；
\hspace{23pt}\bullet\,f(2) = f(\left\lfloor \tfrac{2}{2} \right\rfloor)+f(2\bmod2) = f(1)+f(0) = 1+0 = 1 ；
\hspace{23pt}\bullet\,f(3) = f(\left\lfloor \tfrac{3}{2} \right\rfloor)+f(3\bmod2) = f(1)+f(1) = 1+1 = 2 ；
\hspace{23pt}\bullet\,f(4) = f(\left\lfloor \tfrac{4}{2} \right\rfloor)+f(4\bmod2) = f(2)+f(0) = 1+0 = 1 ；
\hspace{23pt}\bullet\,f(5) = f(\left\lfloor \tfrac{5}{2} \right\rfloor)+f(5\bmod2) = f(2)+f(1) = 1+1 = 2 。