The professor Humbertov Moralov wants to make a raffle between the 100 students of his Data Structure class and Pepito (Student of this group) suggests to use the Josephus problem to determine who is the winner of the raffle, but the thing is that you can know beforehand the winning position if you know the value of n (the total of students in the raffle) and the value k (amount of movements to throwing out students from the circle). The price is kind of interesting, the winner won’t have to present the final exam, and for that reason the professor Humbertov proposes the following variant to josephus problem: “Take the student class list, in which the students are numbered from 1 to 100, then, organize this numbers in a circle and begin to count from number 1 until getting the value k (Take into account that you count clockwise), the student with number k in the list is removed from the circle, and now you begin to count from the number of the next student (k + 1), but in counterclockwise, the student with the number in which the count stopped is removed from the circle, and then you repeat the process alternating between counterclockwise and clockwise counting until you get the winner of the raffle”. The professor Humbertov wants to be sure that student that will win the raffle will be Pepito, because Pepito is the best student in his course, and for that reason he must ensure that pepito’s position will be the winning position, so in order to accomplish this you have to calculate the minimum value k that generates that position and help the Professor Humbertov, after this favor he for sure will increase your grades in his class of formal languages and grammars. Input The input contains several test cases. Each test case has only one line, in which there is a positive integer m (1 ≤ m ≤ 100) that represents the position of Pepito in the class list, remember that Pepito is the one who must win the raffle. The input ends with a line containing a zero, which must not be processed. Output For each test case, you have to print in one line the number k that will ensure that Pepito Perez will won the raffle. It’s guaranteed that 1 ≤ k ≤ 103. Sample Input 1 15 30 88 0 Sample Output 115 36 364 750