Description

给定一个数列a：

当n<=2时,a[n]=n

当n>2，且n是奇数时，a[n]=2a[n-1]

当n>2，且n是偶数时，a[n]=a[n-1]+r[n-1]

其中r[n-1]=mex(|a[i]-a[j]|)(1<=i<=j<=n-1)，mex{S}表示最小的不在S集合里面的非负整数。

数列a的前若干项依次为：1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980。

可以证明，对于任意正整数x，只存在唯一一对整数(p,q)满足x=a[p]-a[q]，定义为repr(x)。

比如repr(17)=(6,3)，repr(18)=(16,15)。

现有n个询问，每次给定一个正整数x，请求出repr(x)。

Format

Input

第一行包含一个正整数n(1<=n<=10^5)。

接下来n行，每行一个正整数x(1<=x<=10^9)，表示一个询问。

Output

输出n行，每行两个正整数p,q，依次回答每个询问。

Samples

2
17
18

6 3
16 15