mathematicians-fight-3

Once a Mathematician was trapped by military people during a world war with his forty colleagues. The colleagues were without any weapons, only the mathematician had a knife. And with no weapons they were not able to fight with the military, so they decided to kill themselves rather than being killed by military.
They all decided that they will stand in a circle and the every third person will 
kill himself but the mathematician didn't like this idea and had no intention 
of killing himself. He tried to calculate where should he stand so that he is the last one left.
Note:- Instead of every 3rd position it will be every 2nd position and of course the number of colleagues will be much more than 40.

Input:-
The first line of input is an integer N  that specifies the number of test cases. After that every line contains an integer X  which is the number of colleagues.

Output:-
For each test case generate a line containing the position of the colleagues who survives. Assume that the colleagues have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2.

Constraints:-
1 ≤ N ≤ 1000
5 ≤ X ≤ 100000000

SAMPLE INPUT
4
5
11
45
23987443

SAMPLE OUTPUT
3
7
27
14420455

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def survivor(x):
	if x == 1:
		return 0
	if x % 2 == 0:
		return 2*survivor(x // 2)
	else:
		s = x // 2 + 1
		a = (survivor(s) - 1) % s
		return 2*a

def main():
	for _ in range(int(input())):
		x = int(input())
		print(survivor(x) + 1)

main()


def survivor(x):
	if x == 1:
		return 0
	if x % 2 == 0:
		return 2*survivor(x // 2)
	else:
		s = x // 2 + 1
		a = (survivor(s) - 1) % s
		return 2*a

def main():
	for _ in range(int(input())):
		x = int(input())
		print(survivor(x) + 1)

main()