You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

澜沧江畔的祝酒歌 (简化版)

【题目描述】 在西双版纳澜沧江畔的泼水节盛宴上，傣族同胞们围成一个大圆圈跳起“长桌宴”祝酒舞。参加跳舞的有 $n$ 位客人，他们按顺时针方向依次编号为 $1, 2, 3, \dots, n$。

舞蹈有一个特别的规则：

1. 从 1 号客人开始，跳过他，由他向 2 号客人敬酒，2 号客人随后退出圆圈去休息。
2. 接着跳过 3 号客人，由 3 号向 4 号敬酒，4 号退出。
3. 依此类推，每隔一个人就有一个人退出，直到圆圈中只剩最后一位客人。

这位留到最后的客人将被授予“澜沧江舞王”的称号并获得精美的普洱茶礼包。给定客人的总数 $n$，请你计算出哪位编号的客人会成为“舞王”。

【输入格式】 输入的第一行包含一个整数 $T$，表示测试数据的组数。 接下来的 $T$ 行，每行包含一个正整数 $n$，表示参加宴会的人数。

【输出格式】 对于每组输入，输出一行，包含一个整数，表示最后剩下的客人编号。

【输入样例】

3
5
8
10

【输出样例】

3
1
5

【样例解释】

• 对于 $n=5$： 退出顺序为：2, 4, 1, 5。最后剩下 3 号。
• 对于 $n=8$： 符合 $2^3$ 的规律，第一个人（1号）前面的那个人（8号）被吃掉后重新开始，根据 $2^n$ 规律，最后剩下 1 号。

【数据范围】

• 对于 30% 的数据：$1 \le n \le 10^5$
• 对于 100% 的数据：$1 \le T \le 10^5, 1 \le n \le 10^{18}$