Codona virus is not only infecting humans and animals. It also has a digital version that can effect computers.It is vastly spreading through networks in recent times. It is encrypting all the data in the computer at the bit level.
The cyber geeks discovered that program for the virus is following an algorithm to encrypt the data. The algorithm is as follows.
Every data has a binary representation. The virus is initially changing all the bits in binary to 1 and then starting from second bit it changes every second nonzero bit(setbit) to 0.
It's a circular process i.e. if it reaches the end of bits it continues to count from starting until only one set bit is left in its binary representation.
Here you'll be given the number of bits in the data and you have to print the position of the bit that is left over by the virus.
For suppose of the number of bits is 5 then it sets all 5 bits to 1 as "11111" then it starts changing the value to 0 from second bit onwards and it becomes as
"10101" after one round then it becomes "00100" after the second round. And stops as only one set bit is left. So 3 will be the answer.
For more clarification in the above 5 set bits, the 2nd bit will be attacked and become 0. Then 4th, 1st and then 5th bit will be 0. So the 3rd bit is left off.
Round 1: 11111 -> 10111 -> 10101
Round 2: 10101 -> 00101 -> 00100 (encryption stops here as only one set bit is left)
The sequence of position of bits set to 0 will be
2nd->4th->1st->5th.
3rd is left over and it will be the answer.
For 7 it will be like:
Round 1: "1111111" -> "1011111" -> "1010111" -> "1010101"
Round 2:"1010101" -> "0010101" -> "0010001"
Round 3:-> "0010001" -> "0000001"
The sequence of bits set to 0 will be
2nd -> 4th -> 6th ->1st -> 5th -> 3rd
7th bit is the only set bit left over. So answer is 7.
Input Format:
The first line of the input contains an integer N denoting the number of files.
Next line contains N integers denoting the number of bits in each file.
Output Format:
Print the position of the leftover bit of each file in new line.
Constraints:
1 <= N <= 1000
1 <= Number of bits of a file <= 50
