There is a game "Choose a number and win money", in which, a person playing a game has to select a number N and he/she will be awarded some money in Rupees accordingly. Some of the observations of selecting a number N and money awarded(M) are:-
N: 1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24 ..........
M: 3   2   1   6   5   4   3   2   1   12   11   10   9     8     7      6      5     4     3    2     1    24  23  22...............
i.e. if you selects a number N=1,she gets M=Rs 3,if N=2,M=Rs 2,if N=3 ,M=Rs 1 and so on..
 
Example 1:
Input:
N = 30
Output:
16
Explanation:
As per the distribution,
you earn Rs 16.
 
 
Example 2:
Input:
N = 1
Output:
3
Explanation:
As per the distribution,
you earn Rs 3.
 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function totalMoney() which takes an integer N and returns total money.
 
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1<=N<=10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Implementation

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

Solutions:
class Solution:

	def totalMoney(ob, N):
		i = 3
		count = 1
		x = 0
		while x <= N:
			i = i * 2
			x = x + i
			count = count + 1
		b = x - i
		return i - (N - b) + 4


class Solution:

	def totalMoney(ob, N):
		j = 3
		k = 3
		while j < N:
			k = k * 2
			j += k
		return j - N + 1


class Solution:

	def totalMoney(ob, N):
		a = 3
		b = a
		while b < N:
			a = a * 2
			b += a
		return b - N + 1


class Solution:

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


class Solution:

	def totalMoney(ob, N):
		arr = [1]
		while arr[-1] < 10 ** 9:
			arr.append(2 * arr[-1] + 2)
		for i in range(len(arr)):
			if N > arr[i]:
				continue
			elif N == arr[i]:
				return arr[i] + 2
			else:
				return arr[i] - N
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.totalMoney(N))


class Solution:

	def totalMoney(ob, N):
		k = 3
		l = 0
		while l + k < N:
			l = l + k
			k = k * 2
		return k + 1 - (N - l)


class Solution:

	def totalMoney(ob, N):
		K = 3
		while N > K:
			N = N - K
			K = K * 2
		return K - N + 1


class Solution:

	def totalMoney(ob, N):
		L = 4
		i = 3
		while N > i * 2:
			i = i * 2
			L += i
		return L - N


class Solution:

	def totalMoney(ob, N):
		test = N
		i = 0
		N_series = 1
		while test >= N_series:
			N_series = N_series + 3 * 2 ** i
			i = i + 1
		j = i - 1
		N_series = 1
		if j == 0:
			N_series = 1
		else:
			for i in range(j):
				N_series = N_series + 3 * 2 ** i
		if N == N_series:
			M = N + 2
		else:
			M = N_series + 2 - (N - N_series)
		return M


class Solution:

	def totalMoney(ob, N):
		max_limit = 4
		index = 3
		while N > index * 2:
			index = index * 2
			max_limit += index
		return max_limit - N