The percentage of Soup boys in India is increasing day by day. These soup boys finally got fed up with girls cheating on them. N girls are randomly chosen and they are now under investigation. Somehow the soup boys found out that, if there are N girls, then the ratio of the number of girls who cheat to the total number of girls is (N-1)/N. As these soup boys are very angry, they wanted to punish all the cheaters. But, obviously, during investigation all the girls claimed to be only one that is good. Soup boys had a plan to find the real good girl. They asked all the girls to form a circle. Then their eyes are tied.  Now the leader of the soup boys goes into the middle of circle, removes the first girl from the group and then turns one step clockwise. Then leaves one girl and removes the second one. Then he leaves two girls and removes the third one and so on. The girl who is left at the end is declared as a good one and is free to go. The rest will await their surprise punishment. Being in the position of a good intelligent girl, you initially want to stand in the position which will get you free. Find such a position.

Input Specification:
The first line contains an integer T denoting the number of test cases. Then T lines follow, each with one integer N, the number of girls soup boys will choose from.

Output Specification:
For each test case output the position the good girl has to stand initially so that will be free at the end.

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 girls arranged in a circle as 1, 2, 3  4, 5. Girl 1 stands right next to 5. Girl 1 is removed first. Then 2 is skipped and 3 removed. The remaining girls will stand in the order 4,5,2. 4 and 5 are skipped and 2 removed. Only 4 and 5 are left and we have to skip three girls this time. We skip 4-5-4 and finally 5 is removed. So the intelligent, good girl should stand initially at 4th position.

---

hide comments

< Previous 1 2 Next >
	kumar_anubhav: 2020-08-05 10:29:52 variant of josephus algorithm :)
	cegprakash: 2019-05-02 09:32:42 @rishabh_hurr: It's in the next page of the comments ;)
	rishabh_hurr: 2019-03-29 08:45:04 @Fata Nugraha can u again send the url of video
	mynk322: 2019-03-19 15:12:30 @Fata: Thanks for the help!! The video is very helpful.... ;-)
	deathgun: 2018-08-13 15:13:12 my 300th! :D
	mastik5h_1998: 2017-09-19 00:29:48 good problem :) normal recursion Last edit: 2017-09-19 00:30:16
	rohit9934: 2017-03-12 17:47:16 Thanks @Fata Nugraha.That video really helped me understanding the problem.BTW adhoc is working fine with o(n) time. Josephus problem using recursion may work but it gives me WA.
	MOHD SALMAN: 2016-02-07 11:13:22 @Fata i think that is only for u, :P
	minhthai: 2016-01-31 17:35:17 java users, u have to implement O(n) using loop to pass
	anuveshkothari: 2015-08-09 21:16:30 learned about josephus problem..