Problem Description

有一张 $n$ 个点的完全无向图，点的标号是 $1...n$，其中边 $(i,j)$ 的长度是 $i~xor~j$，现在你需要求出点 $1$ 到点 $n$ 的最短路的长度。

Input

第一行一个正整数 $T$ 表示数据组数 $1\leq T\leq 100$

对于每组数据：第一行一个正整数 $n$ 表示点数 $(2\leq n\leq 10^5)$

Output

输出 $T$ 行，每行一个整数表示点 $1$ 到点 $n$ 的最短路

1
3

2