Time limit: 1 second Memory limit: 50 megabytes ---------- In a country, the president is elected in the following manner: If $n$ candidates are running $(2 \leq n)$, initially, during a ceremony, each candidate is assigned a number from 1 to $n$ via a lottery. The candidates sit around a table in the order of their assigned numbers, and they are eliminated alternately, starting with number 2. Now, using a recursive function, write a program that takes the number of candidates as input and prints the number of the winning candidate. # Input The number $n$ is given in the sole line of input. $$2 \leq n \leq 100$$ # Output Print the number of the winning candidate in the sole line of output. # Example ## Sample Input 1 ``` 12 ``` ## Sample Output 1 ``` 9 ``` ## Sample Input 2 ``` 16 ``` ## Sample Output 2 ``` 1 ```