Find the Goalkeeper
In a school in 'The land of Nowhere', students love to be the goalkeeper while playing soccer. Coach Randy has designed a method to pick a goal keeper among a givenset of students. He asks them to first stand in a line and assigns them numbers. So, the first in line is given 1, the second is given 2 and so on. Now, he asks them to form a circle. Then, he starts eliminating 'alternate' students starting from 2 (remember, its a circle; so this elimination would occur over and over) . This process continues until only one student is left, who then becomes the goalkeeper. He thinks this is a fair method, but can you do the math to beat his idea ?
Input consists of several input lines. First line has the number of test cases that follow, represented by 't'. Each of the following 't' lines have the total number of students 'n'.
1 < t < 1000000
0 < n < 10000000
For each input, output where should you stand to be selected as the goalkeeper.
Input: 4 1 5 8 12 Output: 1 3 1 9
|Time Limit:||0.236296 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions