该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

Description

有一群进化程度很高的猴子，它们不再通过群殴产生猴王，而是采用一种非常文明的方法选出新的猴王。

猴群里有 n 只猴子，它们在篝火旁围坐成一个圈：其中一只猴子是 1 号，沿顺时针方向依次是 2 号、3 号、……、 n 号，然后回到 1 号。

选举共进行 n-1 轮，每轮出局一只猴子，直到圈中只剩下一只猴子即当选新的猴王。

具体方法如下：

第 1 轮：从 1 号猴子开始按顺时针依次报数，从 1 开始报数，报到 1 就停止且报到 1 的猴子出局；

第 2 轮：从上一轮刚出局猴子的顺时针方向下一个还在圈里的猴子开始重新从 1 开始按顺时针报数，报到 2 就停止且报到 2 的猴子出局；

……

第 k 轮：从上一轮刚出局猴子的顺时针方向下一个还在圈里的猴子开始重新从 1 开始按顺时针报数，报到 k 就停止且报到 k 的猴子出局；

……

第 n-1 轮：从上一轮刚出局猴子的顺时针方向下一个还在圈里的猴子开始重新从 1 开始按顺时针报数，报到 n-1 就停止且报到 n-1 的猴子出局。

此时只剩下一只猴子，它就成为新的猴王。

有一只小猴子很想当上猴王，它想知道自己开始应该是几号才能最后成为新的猴王。

你能帮助它吗？

多组数据。

Input

第一行：一个整数 T，表示数据组数。

接下来 T 行，每行一个正整数 n 。

Output

共 T 行，每组数据的答案占一行。

Sample Input

5
1
2
3
1234
9876543

Sample Output

1
2
2
127
4215815

Hint

共 5 个测试点：

测试点 1（20分）：1 ≤ T ≤ 10, 1 ≤ n ≤ 5,000

测试点 2-3（40分）：1 ≤ T ≤ 10, 1 ≤ n ≤ 5,000,000

测试点 4-5（40分）：T = 2, 1 ≤ n ≤ 50,000,000