Description

给定一个正整数 $n$，求 $\text{mex}\{i\oplus j\}(i,j\in[1,n])$。

此处的 $\text{mex}$ 是指集合中不存在的最小整数。

Format

Input

第一行一个正整数 $t(1\leq t\leq 2\times 10^5)$ 表示数据组数。

接下来 $t$ 行，每行一个正整数 $n(1\leq n\leq 10^{19})$。

Output

共 $t$ 行，每行两个正整数分别表示 $\text{mex}\{i\oplus j\}(i,j\in[1,n])$。

Samples

2
1
3

1
4