Given N people standing in a circle where 1^{st} is having a sword, find the luckiest person in the circle, if, from 1^{st} soldier who is having a sword each has to kill the next soldier and handover the sword to next soldier, in turn, the soldier will kill the adjacent soldier and handover the sword to next soldier such that one soldier remains in this war who is not killed by anyone.
 
Example 1:
Input:
N = 5
Output:
3
Explanation:
In first go 1 3 5 (remains) 
as 2 and 4 killed by 1 and 3. 
In second go 3 will remain 
as 5 killed 1 and 3rd killed 5 
hence, 3 remains alive.
Example 2:
Input:
N = 10
Output:
5
Explanation:
In first 1 3 5 7 9 
remains as 2 4 6 8 10 
were killed by 1 3 5 7 
and 9. In second 1 5 9 
are left as 1 kills 3 
and  5 kill the 7th 
soldier.In third 5th 
soldiers remain alive as 
9 kills the 1st soldier and 
5 kill the 9th soldier.
Your Task:
You don't need to read input or print anything. Your task is to complete the function find() which takes an integer N as input parameter and returns the output as the soldier who was lucky in the game.
 
Expected Time Complexity: O(log N)
Expected Space Complexity: O(1)
 
Constraints:
1<=N<=10^{8}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3
class Solution:
    def find(self,N):
        # code here

Solutions:
class Solution:

	def find(self, N):
		counter = 0
		for i in range(1, N + 1):
			counter = (counter + 2) % i
		return counter + 1


class Solution:

	def find(self, n):
		import math
		len_ = int(math.log(n, 2)) + 1
		n2 = n
		for i in range(len_):
			n2 = n2 ^ 1 << i
		return abs(n - n2)


class Solution:

	def find(self, n):
		a = list(range(1, n + 1))
		i = 0
		size = n
		while len(a) != 1:
			a[:] = [a[i] for i in range(0, size, 2)]
			if size % 2 != 0:
				a.insert(0, a.pop(-1))
			size = len(a)
			i += 1
		return a[0]


import math

class Solution:

	def find(self, N):
		pos = -1
		n = N
		while n > 0:
			n = n >> 1
			pos += 1
		res = N - 2 ** pos
		return res * 2 + 1


class Solution:

	def find(self, N):
		if N == 1:
			return 1
		if N % 2 == 0:
			return 2 * self.find(N / 2) - 1
		else:
			return 2 * self.find(N // 2) + 1


class Solution:

	def find(self, N):
		arr = list(range(1, N + 1))
		while len(arr) > 1:
			if len(arr) % 2 == 0:
				arr = arr[::2]
			else:
				arr = arr[::2]
				arr.insert(0, arr[-1])
				arr.pop()
		return arr[0]


def rec(n):
	if n == 1:
		return 1
	if n & 1:
		return 2 * rec(n // 2) + 1
	return 2 * rec(n // 2) - 1

class Solution:

	def find(self, N):
		return rec(N)


class Solution:

	def find(self, N):
		s = bin(N)[3:]
		s += '1'
		d = 0
		s = s[::-1]
		for i in range(len(s)):
			if s[i] == '0':
				continue
			d += int(pow(2, i))
		return d


import math

class Solution:

	def find(self, n):
		if n == 2 or n == 1:
			return 1
		for i in range(1, n):
			ptr = 2 ** i
			if ptr >= n:
				tem = n - 2 ** (i - 1)
				return tem * 2 + 1


import math

class Solution:

	def find(self, N):
		ans = 0
		if N - 1 & N == 0:
			ans = 1
		else:
			bits = math.floor(math.log(N, 2))
			l = 2 ** bits
			h = 2 ** (bits + 1)
			gap = h - l - 1
			gap_l = N - l
			ans = N - (gap - gap_l)
		return ans


class Solution:

	def find(self, N):
		ans = 1
		while ans <= N:
			ans *= 2
		return 2 * (N - ans // 2) + 1


import math

class Solution:

	def find(self, N):

		def m(N):
			return 2 ** (1 + int(math.floor(math.log2(N))))
		return 2 * N - m(N) + 1


class Solution:

	def find(self, N):
		p = 1
		while p <= N:
			p *= 2
		return 2 * N - p + 1


class Solution:

	def find(self, N):
		a = len(bin(N)) - 3
		return (N - 2 ** a) * 2 + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.find(N))


class Solution:

	def find(self, n):
		k = 1
		while k <= n:
			k *= 2
		return 2 * n - k + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.find(N))


class Solution:

	def find(self, N):
		i = 0
		while 2 ** i <= N:
			i += 1
		i -= 1
		closest = 2 ** i
		ans = (N - closest << 1) + 1
		return ans


class Solution:

	def find(self, N):
		res = 1
		while res <= N:
			res *= 2
		return 2 * (N - res // 2) + 1


from math import log2

class Solution:

	def find(self, N):
		return 2 * (N - 2 ** int(log2(N))) + 1


class Solution:

	def number(self, n):
		lst = [i for i in range(1, n + 1)]
		while len(lst) != 1:
			if len(lst) % 2 == 0:
				lst = lst[::2]
			else:
				lst = lst[::2]
				lst.pop(0)
		return lst[0]

	def find(self, N):
		return self.number(N)


class Solution:

	def find(self, N):
		if N == 1 or N == 2:
			return 1
		i = 4
		while i < N:
			i = 2 * i
		if i == N:
			return 1
		else:
			return N - (i - 1 - N)


import math

class Solution:

	def find(self, N):
		p = 1
		while p <= N:
			p *= 2
		return 2 * N - p + 1


import math

class Solution:

	def find(self, n):
		x = int(math.log(n, 2))
		x = int(math.pow(2, x))
		return 2 * (n - x) + 1


class Solution:

	def find(self, N):
		a = str(bin(N))
		a = a[3:]
		b = a + '1'
		c = int(b, 2)
		return c


class Solution:

	def find(self, N):
		return int(bin(N)[3:] + '1', 2)


class Solution:

	def find(self, N):
		k = 1
		while k < N + 1:
			k *= 2
		return 2 * N - k + 1


class Solution:

	def find(self, N):
		ans = 1
		index = 0
		while N > 1:
			index += 1
			ans += (N & 1) << index
			N >>= 1
		return ans


class Solution:

	def find(self, N):
		(ans, s) = (1, 0)
		while ans <= N:
			ans *= 2
		return 2 * (N - ans // 2) + 1


class Solution:

	def find(self, N):
		z = N
		if N + 1 & N == 0:
			return N
		c = []
		while N > 0:
			a = N % 2
			c.append(a)
			N = N // 2
		a = 2 ** (len(c) - 1)
		return (z - a) * 2 + 1


class Solution:

	def find(self, N):
		ar = list(bin(N).replace('0b', ''))
		ar.append(ar.pop(0))
		return int(''.join(ar), 2)


class Solution:

	def find(self, N):
		z = N
		if N == 2:
			return 1
		else:
			c = 0
			while N > 0:
				a = N & 2
				c = c + 1
				N = N // 2
		return 1 + 2 * (z - 2 ** (c - 1))


class Solution:

	def find(self, n):

		def nn(n):
			i = 1
			while i < n:
				i = i * 2
			if i == n:
				return i
			else:
				return i // 2
		return 2 * (n - nn(n)) + 1


import math

class Solution:

	def find(self, N):
		a = int(math.log2(N))
		a = pow(2, a)
		N = N - a
		return 2 * N + 1


class Solution:

	def find(self, N):
		x = bin(N)
		v = x[2:3]
		x = x[3:] + v
		return int(x, 2)


class Solution:

	def find(self, N):
		a = 1
		while a <= N:
			a *= 2
		return int(2 * (N - a / 2) + 1)


class Solution:

	def find(self, n):
		p = 1
		while p <= n:
			p *= 2
		return 2 * n - p + 1


class Solution:

	def find(self, n):
		p = 1
		while p <= n:
			p *= 2
		return 2 * n - p + 1

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Ll:

	def __init__(self):
		self.head = None

	def insert(self, data):
		nw = Node(data)
		if self.head is None:
			self.head = nw
			nw.next = head
		else:
			h = self.head
			while h.next.data is not head.data:
				h = h.next
			h.next = nw
			nw.next = self.head