All Submissions


The Placement Process at BIT Mesra is at the peak. Soon companies will be visiting for Interns. Apparently they have a new Intern Selection Process. The applicants are made to sit in a circle. Their eyes are tied. The interviewer stands in the middle and starts rejecting candidates. He rejects the first applicant in the circle and then turns one step clockwise. Then he rejects the next 2nd applicant in the circle. Then he rejects the next 3rd applicant and so on.

The applicant who is surviving finally at last gets the Internship offer. Being a smart one, you initially stand in the position in which you will not get rejected. Find such a position.

Input Specification

The first line contains an integer T denoting the number of test cases followed by T test cases each with one integer n - the number of applicants.

Output Specification

For each test case output the position where you have to sit initially, to be selected as an Intern.

Input Constraints

  • T<=250
  • n<=100000


Sample Input


3
2
1
5


Sample Output


2
1
4


Explanation of third test case:

There are 5 applicants arranged in a circle as 1, 2, 3, 4, 5. Applicant 1 stands right to applicant 5. Applicant 1 is shot first. Then the next second applicant (after the last shot applicant) is applicant 3. So he gets shot. The remaining applicants will stand in the order 4, 5, 2. Then the next third applicant is applicant 2 and he gets shot. Now the applicants look in the order 4, 5 and we have to shoot the next 4th applicant. We can see that the order of applicants as 4,5,4,5. Hence the applicant 5 is shot! So the smart applicant should stand initially at 4th position.

Problem Setter : Rounak Tibrewal


Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0