Josephus Problem - Last Knight Standing

You are given a number n representing the number of knights standing in a circle. Starting from the first knight, each knight eliminates the next knight in the circle until only one knight remains. Your task is to determine the position of the last remaining knight using the famous Josephus problem recurrence:

$$J(1)=1$$ $$J(n)=\left(\big(J(n-1)+1\big) \mod n\right) + 1$$

For example, if n = 5, then the final knight stands at position 3. Solve this problem for multiple test cases.

inputFormat

The first line contains an integer T representing the number of test cases.

Each of the following T lines contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of knights in the circle for that test case.

outputFormat

For each test case, output the position of the last remaining knight, each on its own line.

## sample

1
5

3

</p>