I Need Internship
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.
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.
For each test case output the position where you have to sit initially, to be selected as an Intern.
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