Dazzler has a blank canvas and (N-1) colours numbered from 2 to N.  
Let B denote the *beauty* of the canvas. The *beauty* of a blank canvas is 1.

Dazzler paints the canvas by using all the (N-1) colours exactly once. On applying the i^{th} colour (2 ≤ i ≤ N):
If i is odd, B = B \& i.
If i is even, B = B \oplus i. 

Find the *beauty* of the canvas after applying all (N-1) colours.

Note: The colours are applied in ascending order. Colour number 2 is applied first. The i^{th} numbered colour is applied after (i-1)^{th} numbered colour for all i > 2.

Here \& and \oplus denote the [bitwise AND] and [bitwise XOR] operations respectively.

------ Input Format ------ 

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, a single integer N.

------ Output Format ------ 

For each test case, output a single integer, the *beauty* of the canvas after applying all (N-1) colours.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{16}$

----- Sample Input 1 ------ 
2
4
10

----- Sample Output 1 ------ 
7
3

----- explanation 1 ------ 
Initially, $B = 1$.
- On applying colour $2$: Since $2$ is even, $B = B \oplus 2 = 1 \oplus 2 = 3$.
- On applying colour $3$: Since $3$ is odd, $B = B \& 3 = 3 \& 3 = 3$.
- On applying colour $4$: Since $4$ is even, $B = B \oplus 4 = 3 \oplus 4 = 7$.
- On applying colour $5$: Since $5$ is odd, $B = B \& 5 = 7 \& 5 = 5$.
- On applying colour $6$: Since $6$ is even, $B = B \oplus 6 = 5 \oplus 6 = 3$.
- On applying colour $7$: Since $7$ is odd, $B = B \& 7 = 3 \& 7 = 3$.
- On applying colour $8$: Since $8$ is even, $B = B \oplus 8 = 3 \oplus 8 = 11$.
- On applying colour $9$: Since $9$ is odd, $B = B \& 9 = 11 \& 9 = 9$.
- On applying colour $10$: Since $10$ is even, $B = B \oplus 10 = 9 \oplus 10 = 3$.

Test case $1$: There are $3$ colours numbered $2, 3,$ and $4$. Initially, $B = 1$.  
The final beauty of the canvas is $7$.

Test case $2$: There are $9$ colours numbered $2, 3, 4, 5, 6, 7, 8, 9,$ and $10$. Initially, $B = 1$.  
The final beauty of the canvas is $3$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 2 or n % 4 == 3:
		print(3)
	else:
		print(n)


T = int(input())
for Akash in range(T):
	N = int(input())
	if N % 4 == 0:
		print(N + 3)
	elif N % 4 == 1:
		print(N)
	elif N % 4 == 2 or N % 4 == 3:
		print(3)


t = int(input())
for tc in range(t):
	n = int(input())
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	elif n % 4 == 2 or n % 4 == 3:
		print(3)


for x in range(0, int(input())):
	n = int(input())
	value = 1
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	else:
		print(3)


def axnodr(n):
	if n % 4 == 0:
		return n + 3
	elif n % 4 == 1:
		return n
	else:
		return 3
for _ in range(int(input())):
	n = int(input())
	print(axnodr(n))


for _ in range(int(input())):
	n = int(input())
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	else:
		print(3)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 4 == 2 or n % 4 == 3:
		print(3)
	elif n % 4 == 0:
		print(n + 3)
	else:
		print(n)


t = int(input())
while t > 0:
	n = int(input())
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	else:
		print(3)
	t = t - 1


t = int(input())
while t:
	x = int(input())
	if (x - 2) % 4 == 0 or (x - 3) % 4 == 0:
		print(3)
	elif x % 2 != 0:
		print(x)
	else:
		print(x + 3)
	t -= 1


t = int(input())
while t:
	n = int(input())
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	elif n % 4 == 2 or n % 4 == 3:
		print(3)
	t -= 1


def solution(n):
	if n % 4 == 0:
		return n + 3
	if n % 4 == 1:
		return n
	return 3
for _ in range(int(input())):
	n = int(input())
	print(solution(n))


def f(n):
	if n % 4 == 0:
		return n + 3
	if n % 4 == 1:
		return n
	else:
		return 3
t = int(input())
while t:
	n = int(input())
	print(f(n))
	t -= 1


for i in range(int(input())):
	m = int(input())
	p = m % 4
	if p == 3:
		print(3)
	elif p == 2:
		print(3)
	elif p == 0:
		print(3 + m)
	else:
		print(m)


T = int(input())
for i in range(T):
	N = int(input())
	if N % 4 == 3 or N % 4 == 2:
		print(3)
	elif N % 4 == 0:
		print(N + 3)
	else:
		print(N)


for _ in range(int(input())):
	n = int(input())
	if (n - 0) % 4 == 0:
		print(n + 3)
	if (n - 1) % 4 == 0:
		print(n)
	if (n - 2) % 4 == 0 or (n - 3) % 4 == 0:
		print(3)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	else:
		print(3)


for _ in range(int(input())):
	n = int(input())
	d4 = (n - 2) // 4
	r4 = (n - 2) % 4
	if r4 < 2:
		print(3)
	else:
		print(11 + d4 * 4 - 2 * r4)


for i in range(int(input())):
	a = int(input())
	if a % 4 == 0:
		print(a + 3)
	elif a % 4 == 1:
		print(a)
	elif a % 4 == 2:
		print(3)
	else:
		print(3)


for tc in range(int(input())):
	n = int(input())
	b = 1
	test = 0
	if n % 2 == 0 and (n - 2) % 4 == 0:
		b = 3
	elif n % 2 != 0 and (n - 3) % 4 == 0:
		b = 3
	elif n % 2 == 0:
		b = n + 3
	else:
		b = n
	print(b)


for _ in range(int(input())):
	a = int(input())
	if a % 2 == 0 and (a - 2) % 4 == 0 or (a % 2 != 0 and (a - 3) % 4 == 0):
		print(3)
	elif a % 2 == 0:
		print(a + 3)
	else:
		print(a)


t = int(input())
for i in range(t):
	n = int(input())
	b = 1
	if n % 4 == 0:
		print(n + 3)
	elif n % 4 == 1:
		print(n)
	elif n % 4 == 2 or n % 4 == 3:
		print(3)


T = int(input())
for i in range(T):
	N = int(input())
	if N % 4 == 0:
		print(N + 3)
	elif N % 4 == 1:
		print(N)
	else:
		print('3')


for i in range(int(input())):
	n = int(input())
	if n % 4 == 2 or n % 4 == 3:
		print(3)
	elif n % 4 == 1:
		print(n)
	else:
		print(n + 3)


t = int(input())
for i in range(t):
	x = int(input())
	if x % 4 == 1:
		print(x)
	elif x % 4 == 2 or x % 4 == 3:
		print(3)
	else:
		print(x + 3)


for _ in range(int(input())):
	n = int(input())
	b = 1
	if n % 4 == 0:
		print(n + 3)
	if n % 4 == 1:
		print(n)
	if n % 2 == 0 and n % 4 != 0:
		print(3)
	if n % 2 == 1 and n % 4 == 3:
		print(3)


for t in range(int(input())):
	n = int(input())
	ans = 0
	if (n - 2) % 4 <= 1:
		ans = 3
	elif (n - 2) % 4 == 2:
		ans = 3 ^ n
	elif (n - 2) % 4 == 3:
		ans = (3 ^ n - 1) & n
	print(ans)


for tc in range(int(input())):
	N = int(input())
	m = N % 4
	if m == 0:
		print(N + 3)
	elif m == 1:
		print(N)
	else:
		print(3)


t = int(input())
for _ in range(t):
	n = int(input())
	b = 3
	r = n // 2
	if r % 2 == 0:
		b = b ^ r * 2
	i = n % 2
	if i != 0:
		b = b & n
	print(b)