在动物行为学中，Alpha对应动物群体中等级最高的个体，简而言之，就是人赢，那么AlphaGo自然就是人赢狗了。

但是狗群中还有众多的SingleDog，平日里他们和AlphaGo和谐相处，忍受着酸臭味自得其乐的活下去。但在2月14日这天，当AlphaGo在SingleDog们最后的防线——朋友圈秀恩爱的时候，他们实在按耐不住，决定密谋用FFF团的黑暗力量，打败AlphaGo。

但是AlphaGo的智商很高，很快便拦截了SingleDog们传输消息的异或值。为了让AlphaGo相信，SingleDog们只是在数朋友圈里的狗粮数，你，勇敢无畏的跳蚤，决定编造一个弥天大谎。

AlphaGo截获的是一个整数 $n$，你需要构造一个长度大于 $1$ 的区间 $[L,R]$ 使得区间中所有整数的异或和恰好为 $n$。

输入格式

第一行输入一个整数 $t$ 表示数据组数。

接下来 $t$ 行每行一个整数 $n$。

输出格式

每组数据输出两个空格隔开的整数 $L,R$，表示你构造的区间。要求 $1\le L<R\le {10}^{18}$。

输入保证存在这样的区间。

样例

input

3
0
4
12

output

8 67
97 100
87 90

限制与约定

对于 $100\mathrm{\%}$ 的数据，$n\ge 0,1\le t\le 100$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载