Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing $N$ gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:  Take one gold coin from the chest.  Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even. 

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.


-----Input-----

The first line contains a single integer $T$ $(1 \le T \le 10^5)$ denotes the number of test cases.

The next $T$ lines each contain a single integer $N$ $(1 \le N \le 10^{18})$.


-----Output-----

$T$ lines, each line is the answer requested by Mr. Chanek.


-----Example-----
Input
2
5
6

Output
2
4



-----Note-----

For the first case, the game is as follows:   Mr. Chanek takes one coin.  The opponent takes two coins.  Mr. Chanek takes one coin.  The opponent takes one coin. 

For the second case, the game is as follows:   Mr. Chanek takes three coins.  The opponent takes one coin.  Mr. Chanek takes one coin.  The opponent takes one coin.

Source: codeforces | Difficulty: MEDIUM
Tags: Game theory

Greedy algorithms


Solutions:
input = __import__('sys').stdin.readline
x = int(input())
for i in range(x):
	n = int(input())
	s = 0
	k = 1
	while n:
		if n % 2 == 1 or (n > 4 and n % 4 == 0):
			n = n - 1
			t = 1
		else:
			t = n // 2
			n = n // 2
		if k:
			s = s + t
			k = 0
		else:
			k = 1
	print(s)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
input = __import__('sys').stdin.readline
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def egcd(a, b):
	(x, y, u, v) = (0, 1, 1, 0)
	while a != 0:
		(q, r) = (b // a, b % a)
		(m, n) = (x - u * q, y - v * q)
		(b, a, x, y, u, v) = (a, r, u, v, m, n)
	gcd = b
	return (gcd, x, y)
primes = list(map(int, '\n2      3      5      7     11     13     17     19     23     29 \n     31     37     41     43     47     53     59     61     67     71 \n     73     79     83     89     97    101    103    107    109    113 \n    127    131    137    139    149    151    157    163    167    173 \n    179    181    191    193    197    199    211    223    227    229 \n    233    239    241    251    257    263    269    271    277    281 \n    283    293    307    311    313    317    331    337    347    349 \n    353    359    367    373    379    383    389    397    401    409 \n    419    421    431    433    439    443    449    457    461    463 \n    467    479    487    491    499    503    509    521    523    541 \n    547    557    563    569    571    577    587    593    599    601 \n    607    613    617    619    631    641    643    647    653    659 \n    661    673    677    683    691    701    709    719    727    733 \n    739    743    751    757    761    769    773    787    797    809 \n    811    821    823    827    829    839    853    857    859    863 \n    877    881    883    887    907    911    919    929    937    941 \n    947    953    967    971    977    983    991    997   1009\n    '.split()))
primes_set = set(primes)

def solve():
	n = inp()
	ch = 0
	ch_turn = True
	while n > 0:
		if n % 4 == 0 and n > 8:
			n -= 1
			if ch_turn:
				ch += 1
		elif n % 2 == 0:
			n //= 2
			if ch_turn:
				ch += n
		else:
			n -= 1
			if ch_turn:
				ch += 1
		ch_turn = not ch_turn
	print(ch)

def main():
	tests = inp()
	for _ in range(tests):
		solve()
main()


from sys import stdin
input = stdin.readline

def max_pos_coins(n):
	a = 0
	while n != 0:
		if n == 4:
			a += 3
			n = 0
			continue
		if n % 4 == 0:
			n -= 2
			a += 1
		else:
			a += n // 2
			n = n // 2 - 1
	return a
for _ in range(int(input())):
	n = int(input())
	print(max_pos_coins(n) if n % 2 == 0 else n - max_pos_coins(n - 1))


import sys
import bisect
from bisect import bisect_right
import math
from sys import stdin, stdout

def sieve(N):
	primeNumbers = [True] * (N + 1)
	primeNumbers[0] = False
	primeNumbers[1] = False
	i = 2
	while i * i <= N:
		j = i
		if primeNumbers[j]:
			while j * i <= N:
				primeNumbers[j * i] = False
				j += 1
		i += 1
	return primeNumbers

def getPrime(N):
	primes = sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result

def factor(N):
	factors = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			factors.append(i)
			if i != N // i:
				factors.append(N // i)
		i += 1
	return sorted(factors)

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def extendedGcd(a, b):
	if a < b:
		return extendedGcd(b, a)
	if b == 0:
		return [a, 1, 0]
	res = extendedGcd(b, a % b)
	x = res[2]
	y = res[1] - math.floor(a / b) * res[2]
	res[1] = x
	res[2] = y
	return res

def iterativeModularFunc(a, b, c):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % c
		a = a * a % c
		b = b // 2
	return res

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def Solution(n):
	ans = 0
	while n != 0:
		if n == 4:
			ans += 3
			n = 0
			continue
		if n % 4 == 0:
			n -= 2
			ans += 1
		else:
			ans += n // 2
			n = n // 2 - 1
	return ans

def main():
	for _ in range(get_int()):
		n = get_int()
		ans = 0
		if n % 2 == 0:
			ans = Solution(n)
		else:
			ans = n - Solution(n - 1)
		print(ans)
main()


from sys import stdin, stdout

def INPUT():
	return list((int(i) for i in stdin.readline().split()))

def inp():
	return stdin.readline()

def out(x):
	return stdout.write(x)
import math
import random
import sys

def calc(n):
	ans = 0
	i = 1
	while n:
		m = 0
		if n % 2 == 0 and n // 2 % 2 == 1 or n == 4:
			n //= 2
			m = n
		else:
			n -= 1
			m = 1
		if i:
			ans += m
		i ^= 1
	return ans
for _ in range(int(input())):
	n = int(inp())
	t = calc(n)
	out(str(t) + '\n')


import os
import sys
from collections import Counter
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	for _ in range(int(input())):
		n = int(input())
		chanek = True
		count = 0
		while n > 0:
			if chanek == True:
				if n % 2 == 0:
					div = n // 2
					if div % 2 == 0 and n > 4:
						count += 1
						n -= 1
					else:
						count += n // 2
						n = n // 2
				else:
					count += 1
					n -= 1
				chanek = False
			elif chanek == False:
				if n % 2 == 0:
					div = n // 2
					if div % 2 == 0 and n > 4:
						n -= 1
					else:
						n = n // 2
				else:
					n -= 1
				chanek = True
		print(count)
main()


def solve(x):
	log_2 = (x + 1).bit_length() - 1
	if x < 8:
		return log_2
	return log_2 + bin(x + 1 - (1 << log_2) >> 1 & (1 << log_2 - 2) - 1).count('1')
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n % 2 == 0:
		print(n + 1 - solve(n + 1))
	else:
		print(solve(n))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def get_ints():
	return map(int, sys.stdin.readline().split())
T = int(input())
for _ in range(T):
	n = int(input())
	c = 0
	ans = 0
	while n > 0:
		c += 1
		coin = 0
		if n % 2 == 1 or (n > 4 and n % 4 == 0):
			coin = 1
			n -= 1
		else:
			coin = n // 2
			n = n // 2
		ans += coin * (c % 2)
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
for _ in range(int(input())):
	n = int(input())
	m = 0
	ch = 1
	copy = n
	while n > 0:
		d = 0
		if n % 2 == 1:
			d += 1
			n -= 1
		else:
			n1 = n // 2
			if n1 == 2 or n1 % 2 == 1:
				n //= 2
				d += n
			else:
				n -= 1
				d += 1
		if ch == 1:
			m += d
		ch = 3 - ch
	print(m)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	an = 0
	while n:
		if n % 2:
			n -= 1
			an += 1
			if n % 4 == 0 and n > 4:
				n -= 1
			else:
				n = int(n // 2)
		elif n % 4 == 0 and n > 4:
			n -= 2
			an += 1
		else:
			an += int(n // 2)
			n = int(n // 2)
			n -= 1
	print(an)


T = int(input())
l = []
dp = [0, 1, 1, 2, 3, 2]
for _ in range(T):
	N = int(input())
	ans = 0
	while N > 5:
		if N % 2 == 1:
			ans += 1
			N -= 1
			if N % 4 == 0:
				N -= 1
			else:
				N //= 2
		elif N % 4 == 0:
			ans += 1
			N -= 2
		else:
			ans += N // 2
			N //= 2
			N -= 1
	l.append(ans + dp[N])
for i in range(T):
	print(l[i])


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for i1 in range(int(input())):
	n = int(input())
	ans = 0
	turn = 0
	while n > 0:
		if n % 2 == 0 and n % 4 != 0 or n == 4:
			n = n // 2
			this = n
		else:
			n = n - 1
			this = 1
		if turn == 0:
			ans += this
			turn = 1
		else:
			turn = 0
	print(ans)


from os import path
import sys
from collections import defaultdict, Counter
maxx = float('inf')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	I = lambda : int(sys.stdin.buffer.readline())
	tup = lambda : map(int, sys.stdin.buffer.readline().split())
	lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
	S = lambda : sys.stdin.readline().replace('\n', '').strip()
	stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
	star = lambda x: print(' '.join(map(str, x)))
else:
	I = lambda : int(sys.stdin.buffer.readline())
	tup = lambda : map(int, sys.stdin.buffer.readline().split())
	lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
	S = lambda : sys.stdin.readline().replace('\n', '').strip()
	stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
	star = lambda x: print(' '.join(map(str, x)))
for _ in range(I()):
	n = I()
	(ans, cnt) = (0, 0)
	while n > 0:
		if cnt % 2 == 0:
			if n % 2:
				n -= 1
				ans += 1
			elif n % 4 == 0 and n != 4:
				n -= 1
				ans += 1
			else:
				x = n // 2
				ans += x
				n -= x
		elif n % 2:
			n -= 1
		elif n % 4 == 0 and n != 4:
			n -= 1
		else:
			x = n // 2
			n -= x
		cnt += 1
	print(ans)


input = __import__('sys').stdin.readline
for _ in range(int(input())):
	n = int(input())
	ans = 0
	c = 1
	while n:
		r = 0
		if n % 2 == 0 and n // 2 % 2 or n == 4:
			n //= 2
			r = n
		else:
			r = 1
			n -= 1
		if c:
			ans += r
		c ^= 1
	print(ans)


ans = []

def solve(n):
	f = s = 0
	fs = True
	if n & 1:
		n -= 1
		fs = False
	while n:
		if n == 4:
			f += 3
			s += 1
			n = 0
		elif n // 2 & 1:
			f += n // 2
			s += 1
			n = n // 2 - 1
		else:
			f += 1
			s += 1
			n -= 2
	ans.append([s + 1, f][fs])
coins = []
for _ in range(int(input())):
	coins.append(int(input()))
for i in coins:
	if i == 1:
		ans.append(1)
	else:
		solve(i)
print('\n'.join(map(str, ans)))


t = int(input())
ans = []
pass
for case in range(t):
	gold = [0, 0]
	n = int(input())
	i = 0
	while n > 0:
		if n % 4 == 0 and n > 4:
			gold[i] += n // 2
			gold[1 - i] += 1
			n = n // 2 - 1
		elif n % 2 == 0:
			gold[i] += n // 2
			n = n // 2
		else:
			gold[i] += 1
			n -= 1
		i = (i + 1) % 2
	ans.append(str(gold[0]))
print('\n'.join(ans))


import sys
import os
from math import sqrt, log, log2, log10, gcd, floor, pow, sin, cos, tan, pi, inf, factorial
from copy import copy, deepcopy
import bisect
from sys import exit, stdin, stdout
from collections import Counter, defaultdict, deque
from itertools import permutations
import heapq
mod = 1000000007
iinp = lambda : int(sys.stdin.readline())
inp = lambda : sys.stdin.readline().strip()
strl = lambda : list(inp().strip().split(' '))
intl = lambda : list(map(int, inp().split(' ')))
mint = lambda : map(int, inp().split())
flol = lambda : list(map(float, inp().split(' ')))
flush = lambda : stdout.flush()

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	p = int(sqrt(n))
	for i in range(5, p + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def solve():
	n = iinp()
	ans = 0
	while n:
		if n == 4:
			ans += 3
			return ans
		if n % 2 == 1:
			ans += 1
			n -= 1
		elif n // 2 % 2 == 1:
			ans += n // 2
			n //= 2
		else:
			ans += 1
			n -= 1
		if n:
			if n == 4:
				ans += 1
				return ans
			if n % 2:
				n -= 1
			elif n // 2 % 2:
				n //= 2
			else:
				n -= 1
	return ans
for _ in range(iinp()):
	print(solve())


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	num = 0
	c = 1
	while n > 0:
		if n % 2 == 0 and n // 2 % 2 or n == 4:
			n = n // 2
			r = n
		else:
			n -= 1
			r = 1
		if c:
			num += r
		c ^= 1
	ans.append(num)
print('\n'.join((str(x) for x in ans)))


def chanek(n):
	chanek = 0
	while n > 0:
		if n == 4:
			chanek += 3
			break
		elif n % 4 == 0:
			chanek += 1
			n -= 2
		elif n % 2 == 0:
			chanek += n // 2
			n = n // 2 - 1
	return chanek
from sys import stdin
input = stdin.readline
for t in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(chanek(n))
	else:
		print(n - chanek(n - 1))


from sys import stdin
input = stdin.readline

def funciona(n):
	ans = 0
	while n != 0:
		if n == 4:
			ans += 3
			n = 0
			continue
		elif n % 4 == 0:
			ans += 1
			n -= 2
		else:
			ans += n // 2
			n -= n // 2 + 1
	return ans
for _ in range(0, int(input())):
	n = int(input())
	if n % 2 == 1:
		print(n - funciona(n - 1))
	else:
		print(funciona(n))


t = int(input())
o = []
a = [0] * (5 * 10 ** 5)
a[0] = 1
a[1] = 2
a[2] = 2
a[3] = 3
a[4] = 4
a[5] = 3
for i in range(6, 5 * 10 ** 5):
	if i % 2:
		a[i] = a[(i - 1) // 2] + 1
	else:
		a[i] = a[(i - 1) // 2] + 2

def f(k):
	s = 0
	while k > 10 ** 6:
		k = (k - 1) // 2
		s += 1
		if k % 2 == 0:
			k -= 1
			s += 1
	s += a[(k - 1) // 2]
	return s
for i in range(t):
	m = int(input())
	s = 0
	if m % 2 == 0:
		if m % 4 == 2:
			o += [str(m - f(m // 2))]
		elif m == 4:
			o += ['3']
		else:
			o += [str(m - 1 - f(m // 2 - 1))]
	else:
		o += [str(f(m))]
print('\n'.join(o))


d = {0: 0, 2: 1, 4: 1}
inp = []
ans = []

def search(i):
	t = 0
	while i not in d:
		t += 1
		if i % 4 == 0:
			i -= 2
		else:
			i = i // 2 - 1
	return t + d[i]
for time in range(int(input())):
	i = int(input())
	if i % 2 == 0:
		ans.append(i - search(i))
	else:
		ans.append(1 + search(i - 1))
print('\n'.join(list(map(str, ans))))


import sys
input = sys.stdin.readline
from sys import stdin, stdout
from collections import defaultdict, Counter
M = 10 ** 9 + 7

def main():
	for _ in range(int(input())):
		n = int(input())
		ans = 0
		while n:
			if n % 2 == 1:
				n -= 1
				ans += 1
				if n % 4 == 0 and n >= 12:
					n -= 1
				else:
					n //= 2
			elif n % 4 == 0 and n >= 12:
				n -= 1
				ans += 1
				n -= 1
			else:
				ans += n // 2
				n //= 2
				if n % 2 == 1:
					n -= 1
				elif n % 4 == 0 and n >= 12:
					n -= 1
				else:
					n //= 2
		print(ans)
main()


from sys import stdin

def f(n):
	c = 0
	while n > 1:
		if n % 4 == 1:
			if n == 5:
				c += 1
				n -= 3
			else:
				c += 1
				n -= 2
		elif n % 4 == 3:
			c += 1
			n -= (n + 1) // 2
		elif n % 4 == 2:
			c += n // 2
			n -= (n + 2) // 2
		elif n % 4 == 0:
			if n == 4:
				c += 2
				n -= 3
			else:
				c += 1
				n -= 2
	if n == 1:
		return c + 1
	return c
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	print(f(n))


input = __import__('sys').stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	turn = 0
	while n > 0:
		coin = 0
		turn += 1
		if n % 2 == 1 or (n > 4 and n % 4 == 0):
			coin = 1
			n -= 1
		else:
			coin = n // 2
			n = n // 2
		ans += coin * (turn % 2)
	print(ans)


from sys import stdin
n = int(stdin.readline())
for _ in range(n):
	ans = 0
	turn = 1
	start = int(stdin.readline())
	while start > 0:
		if turn:
			turn = 0
			if start % 4 == 2 or start == 4:
				ans += start // 2
				start = start // 2
			else:
				start -= 1
				ans += 1
		else:
			turn = 1
			if start % 4 == 2 or start == 4:
				start = start // 2
			else:
				start -= 1
	print(ans)


from sys import stdin
input = stdin.readline

def game(n):
	p1 = 0
	p2 = 0
	i = 1
	while n:
		if n % 4 == 0 and n > 8:
			p1 += 1
			n -= 2
		elif n % 2 == 0:
			p1 += n // 2
			n = n // 2
			if n % 2 == 0:
				n //= 2
			else:
				n -= 1
		else:
			p1 += 1
			n -= 1
			if n % 4 == 0 and n > 8:
				n -= 1
			elif n % 2 == 0:
				n //= 2
	return p1
t = int(input())
for u in range(t):
	n = int(input())
	print(game(n))


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint

def main():
	n = int(input())
	bol = False
	res = 0
	if n % 2:
		n -= 1
		bol = True
	opr = 0
	t = n
	while n:
		if n == 4:
			opr += 3
			n = 0
		elif n // 2 % 2 == 0:
			opr += 1
			n -= 2
		else:
			opr += n // 2
			n = n // 2
			n -= 1
	if bol:
		print(1 + (t - opr))
	else:
		print(opr)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


input = __import__('sys').stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	i = 1
	(A, B) = (0, 0)
	while n:
		if i % 2:
			if n % 4 == 0 and n > 4 or n % 2:
				A += 1
				n -= 1
			elif n % 2 == 0:
				n //= 2
				A += n
		elif n % 4 == 0 and n > 4 or n % 2:
			B += 1
			n -= 1
		elif n % 2 == 0:
			n //= 2
			B += n
		i += 1
	print(A)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	cur = 0
	turn = 0
	while n > 0:
		if turn == 0:
			if n % 4 == 0 and n > 8:
				cur += 1
				n -= 1
			elif n % 2 == 0:
				cur += n // 2
				n //= 2
			else:
				cur += 1
				n -= 1
			turn = 1
		else:
			if n % 4 == 0 and n > 8:
				n -= 1
			elif n % 2 == 0:
				n //= 2
			else:
				n -= 1
			turn = 0
	print(cur)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	n2 = n
	coins = 0
	while n:
		if n == 4:
			coins += 3
			break
		if n % 2 == 1:
			n -= 1
			continue
		if n % 4 == 0:
			coins += 1
			n -= 1
			continue
		if n % 2 == 0:
			coins += n // 2
			n = n // 2
			continue
	if n2 % 2 == 0:
		print(coins)
	else:
		print(n2 - coins)


dic = {0: 0}
for k in range(1, 100000):
	if k % 2 == 0:
		dic[k] = k - min(dic[k - 1], dic[k // 2])
	else:
		dic[k] = k - dic[k - 1]
T = int(input())
a = []
for i in range(T):
	N = int(input())
	ans = 0
	while N >= 100000:
		if N % 2 != 0:
			ans += 1
			N -= 1
			if N % 4 != 0:
				N //= 2
			else:
				N -= 1
		elif N % 4 == 0:
			ans += 1
			N -= 2
		else:
			ans += N // 2
			N = N // 2 - 1
	a.append(ans + dic[N])
for x in a:
	print(x)


BUFSIZE = 8192
import os
import sys
import math
from io import BytesIO, IOBase
from bisect import bisect_left
from bisect import bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	c = 0
	f = 0
	while n > 0:
		f += 1
		if n % 2 == 1 or (n % 4 == 0 and n > 5):
			if f % 2 == 1:
				c += 1
			n -= 1
		else:
			if f % 2 == 1:
				c += n // 2
			n = n // 2
	print(c)


out = []
for i in range(int(input())):
	(C, flag) = (0, 1)
	coin = int(input())
	while coin > 0:
		public = 0
		if coin % 2 == 0 and coin // 2 % 2 or coin == 4:
			coin //= 2
			public = coin
		else:
			public = 1
			coin -= 1
		if flag:
			C += public
		flag ^= 1
	out.append(C)
print('\n'.join(map(str, out)))


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
getcontext().prec = 30
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	a = int(input())
	z = a
	r = False
	if a % 2:
		r = not r
		a -= 1
	t = 0
	while a:
		if a == 4:
			a = 0
			t += 3
			continue
		if a % 4 == 0:
			t += 1
			a = a - 2
		elif a % 2 == 0:
			t += a // 2
			a = a // 2 - 1
		else:
			a -= 1
			t += 1
	if r:
		print(z - t)
	else:
		print(t)


input = __import__('sys').stdin.readline
for x in range(int(input())):
	n = int(input())
	z = 0
	t = n
	if n % 2:
		n -= 1
	while n > 0:
		if n % 2:
			n -= 1
			n //= 2
			z += 1
		elif n // 2 % 2 == 1 or n == 4:
			n //= 2
			z += n
			n -= 1
		else:
			n -= 2
			n //= 2
			z += 1 + n
			n -= 1
	print(z if t % 2 == 0 else t - z)


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
for _ in range(getInt()):
	res = 0
	n = getInt()
	nn = n
	if n & 1:
		res += 1
		n -= 1
	while n:
		res += 1
		if n < 5:
			break
		if n >> 1 & 1:
			n >>= 1
			n -= 1
		else:
			n -= 2
	if nn & 1:
		print(res)
	else:
		print(nn - res)


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = int(input())
	cIsNext = True
	ans = 0
	while n > 0:
		change = 1
		if n % 2 == 0:
			if n % 4 == 0 and n // 4 > 2:
				change = 1
			else:
				change = n // 2
		n -= change
		if cIsNext:
			ans += change
		cIsNext = not cIsNext
	print(ans)


t = int(input())
golds = []
for _ in range(t):
	golds.append(int(input()))
ans = []

def optimum(left):
	greedy_first = 0
	greedy_second = 0
	fs = True
	if left & 1 == 1:
		left -= 1
		fs = False
	while left:
		if left == 4:
			greedy_first += 3
			greedy_second += 1
			left = 0
		elif left // 2 & 1:
			greedy_first += left // 2
			greedy_second += 1
			left = left // 2 - 1
		else:
			greedy_first += 1
			greedy_second += 1
			left -= 2
	ans.append([greedy_second + 1, greedy_first][fs])
for gold in golds:
	if gold == 1:
		ans.append(1)
	else:
		optimum(gold)
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
ans = []
for _ in range(t):
	(n,) = I()
	an = 0
	while n:
		if n == 4:
			an += 3
			break
		if n % 2:
			an += 1
			n -= 1
		elif n // 2 % 2:
			an += n // 2
			n //= 2
		else:
			an += 1
			n -= 1
		if n:
			if n == 4:
				an += 1
				break
			if n % 2:
				n -= 1
			elif n // 2 % 2:
				n //= 2
			else:
				n -= 1
	ans.append(str(an))
sys.stdout.write('\n'.join(ans))


dic = {0: 0}
for k in range(1, 100000):
	if k % 2 == 0:
		dic[k] = k - min(dic[k - 1], dic[k // 2])
	else:
		dic[k] = k - dic[k - 1]

def cal(x):
	if x < 100000:
		return dic[x]
	elif x % 4 == 0:
		return cal(x // 2 - 2) + x // 2
	elif x % 4 == 1:
		return cal(x // 2 - 1) + 2
	elif x % 4 == 2:
		return cal(x // 2 - 1) + x // 2
	else:
		return cal(x // 2) + 1
T = int(input())
a = []
for i in range(T):
	N = int(input())
	a.append(cal(N))
for x in a:
	print(x)


import itertools

def f(x):
	scores = [0, 0]
	for i in itertools.cycle([0, 1]):
		if x & 1:
			scores[i] += 1
			x -= 1
		elif x == 0:
			return scores[0]
		elif x == 4 or x & 2:
			x >>= 1
			scores[i] += x
		else:
			x -= 1
			scores[i] += 1
N = int(input())
results = []
import sys
for n in map(f, map(int, sys.stdin.read().split())):
	results.append(n)
print('\n'.join(map(str, results)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	res = 0
	n = N()
	nn = n
	if n & 1:
		res += 1
		n -= 1
	while n:
		res += 1
		if n < 5:
			break
		if n >> 1 & 1:
			n >>= 1
			n -= 1
		else:
			n -= 2
	if nn & 1:
		print(res)
	else:
		print(nn - res)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fnxn(n):
	ans = 0
	while n:
		if n in dp:
			ans += dp[n]
			n = 0
		elif n % 4 == 0:
			ans += 1
			n -= 2
		elif n % 2 == 0:
			n //= 2
			ans += n
			n -= 1
		else:
			ans += 1
			n -= 1
	return ans
cases = int(input())
dp = {1: 1, 2: 1, 3: 2, 4: 3}
for t in range(cases):
	n = int(input())
	if n % 2 == 0:
		print(fnxn(n))
	else:
		print(n - fnxn(n - 1))


import sys
input = sys.stdin.readline

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input().strip()

def listStr():
	return list(input().strip())
import collections as col
import math

def solve():
	N = getInt()
	ans = 0
	flag = False
	while N:
		flag = not flag
		if N == 1:
			return ans + 1 if flag else ans
		if N == 2:
			return ans + 1
		if N == 4:
			return ans + 3 if flag else ans + 1
		if N % 2 == 1 or N % 4 == 0:
			N -= 1
			if flag:
				ans += 1
			continue
		N //= 2
		if flag:
			ans += N
for _ in range(getInt()):
	print(solve())


n = int(input())
ans = []
dp = [0] * 100001
for i in range(1, 100001):
	if i % 2 == 0:
		dp[i] = i - min(dp[i - 1], dp[i // 2])
	else:
		dp[i] = i - dp[i - 1]
for i in range(n):
	a = int(input())
	e = 0
	while a > 100000:
		if a % 2 != 0:
			e += 1
			a -= 1
			if a % 4 != 0:
				a //= 2
			else:
				a -= 1
		elif a % 4 == 0:
			e += 1
			a -= 2
		else:
			e += a // 2
			a //= 2
			a -= 1
	e += dp[a]
	ans.append(str(e))
print('\n'.join(ans))


def main():
	memo = {1: 1, 2: 1, 3: 2, 4: 3}
	return '\n'.join(map(str, (Chanek_s_nCoins(int(input()), memo) for _ in range(int(input())))))

def Chanek_s_nCoins(nCoins, memo):
	if nCoins in memo:
		return memo[nCoins]
	if nCoins % 2:
		return 1 + loser_s_nCoins(nCoins - 1)
	return nCoins - loser_s_nCoins(nCoins)

def loser_s_nCoins(nCoins):
	if nCoins < 5:
		return 1
	nCoinsLeft = nCoins // 2
	if nCoinsLeft % 2:
		return 1 + loser_s_nCoins(nCoinsLeft - 1)
	return 2 + loser_s_nCoins(nCoinsLeft - 2)
print(main())


from sys import stdout, stdin
from io import IOBase, BytesIO
from os import read, write, fstat
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size: int=...):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
input = lambda : stdin.readline().rstrip('\r\n')

def max_pos_coins(n):
	a = 0
	while n != 0:
		if n == 4:
			a += 3
			n = 0
			continue
		if n % 4 == 0:
			n -= 2
			a += 1
		else:
			a += n // 2
			n = n // 2 - 1
	return a
for _ in range(int(input())):
	n = int(input())
	print(max_pos_coins(n) if n % 2 == 0 else n - max_pos_coins(n - 1))


def game(n):
	cnt = 0
	while n:
		if n == 4:
			cnt += 3
			n = 0
		elif n == 2 or n % 4 == 0:
			cnt += 1
			n -= 2
		else:
			cnt += n // 2
			n = n // 2 - 1
	return cnt
ans = []
for m in range(int(input())):
	i = int(input())
	if i % 2 == 0:
		ans.append(game(i))
	else:
		ans.append(i - game(i - 1))
print('\n'.join(map(str, ans)))


input = __import__('sys').stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	get = 0
	turn = 0
	while n > 0:
		turn += 1
		a = 0
		if n % 4 == 2 or n == 4:
			get += turn % 2 * (n // 2)
			n //= 2
		else:
			get += turn % 2 * 1
			n -= 1
	print(get)


import sys
l = []
for i in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	result = 0
	flag = 1
	while n:
		if n % 2 == 0 and n // 2 % 2 or n == 4:
			n //= 2
			if flag:
				result += n
		else:
			n -= 1
			if flag:
				result += 1
		flag = 1 - flag
	l.append(result)
print('\n'.join(map(str, l)))


import sys
input = sys.stdin.readline
num = int(input())
for _ in range(num):
	n = int(input())
	ans = 0
	turn = 0
	while n > 0:
		coin = 0
		turn += 1
		if n % 2 == 1 or (n > 4 and n % 4 == 0):
			coin = 1
			n -= 1
		else:
			coin = n // 2
			n = n // 2
		ans += coin * (turn % 2)
	print(ans)


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
for i in range(int(input())):
	s = int(input())
	a = 0
	fl = 0
	while s > 0:
		if fl == 0:
			if s % 4 == 0 and s != 4 or s % 2 != 0:
				a += 1
				s -= 1
				fl = 1
			else:
				a += s // 2
				s //= 2
				fl = 1
		elif s % 4 == 0 and s != 4 or s % 2 != 0:
			s -= 1
			fl = 0
		else:
			s //= 2
			fl = 0
	print(a)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = 0
	while n != 0:
		if n % 4 == 0 and n != 4:
			n -= 2
			a += 1
		elif n % 2 == 0:
			a += n // 2
			n = n // 2 - 1
		else:
			a += 1
			if (n - 1) % 4 == 0 and n > 5:
				n -= 2
			else:
				n //= 2
	print(int(a))


import sys, functools, collections, bisect, math, heapq
input = sys.stdin.readline
sys.setrecursionlimit(300000)

def fun(n):
	if n == 0:
		return (0, 0)
	if n % 2 or (n % 4 == 0 and n > 8):
		(a, b) = fun(n - 1)
		return (1 + b, a)
	else:
		(a, b) = fun(n // 2)
		return (n // 2 + b, a)
t = int(input())
for _ in range(t):
	n = int(input())
	chanek = True
	count = 0
	while n > 0:
		if chanek == True:
			if n % 2 == 0:
				div = n // 2
				if div % 2 == 0 and n > 4:
					count += 1
					n -= 1
				else:
					count += n // 2
					n = n // 2
			else:
				count += 1
				n -= 1
			chanek = False
		elif chanek == False:
			if n % 2 == 0:
				div = n // 2
				if div % 2 == 0 and n > 4:
					n -= 1
				else:
					n = n // 2
			else:
				n -= 1
			chanek = True
	print(count)


from sys import *
input = stdin.readline
import random
from bisect import *
import math
from collections import *
import operator
from heapq import *
from itertools import *
inf = 10 ** 18
mod = 10 ** 9 + 7
for test in range(int(input())):
	n = int(input())
	ans = 0
	t = 0
	while n:
		if n % 2 == 0 and n // 2 % 2 != 0 or n == 4:
			n //= 2
			c = n
		else:
			n -= 1
			c = 1
		if t == 0:
			ans += c
		t ^= 1
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
for ad in range(int(input())):
	n = int(input())
	t = 0
	ans = 0
	while n > 0:
		if t == 0:
			if n % 2 == 0:
				if n == 4:
					ans += 2
					n = 2
				elif n // 2 % 2 == 0:
					ans += 1
					n -= 1
				else:
					ans += n // 2
					n = n // 2
			else:
				n -= 1
				ans += 1
			t = 1
		else:
			if n % 2 == 0:
				if n == 4:
					n = 2
				elif n // 2 % 2 == 0:
					n -= 1
				else:
					n = n // 2
			else:
				n -= 1
			t = 0
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = 1
	ans = 0
	while n > 0:
		if a == 1:
			if n % 2 == 0:
				if n // 2 % 2 == 1 or n == 4:
					ans += n // 2
					n = n // 2
				else:
					ans += 1
					n -= 1
			else:
				ans += 1
				n -= 1
			a = 0
		else:
			if n % 2 == 0:
				if n // 2 % 2 == 1 or n == 4:
					n = n // 2
				else:
					n -= 1
			else:
				n -= 1
			a = 1
	print(ans)


import sys
input = sys.stdin.readline
T = int(input())
result = [''] * T
for i in range(T):
	N = int(input())
	ans = 0
	turn = True
	while N > 0:
		if N % 4 == 2 or N == 4:
			N //= 2
			ans += N * turn
			turn = not turn
		else:
			ans += 1 * turn
			N -= 1
			turn = not turn
	result[i] = str(ans)
print('\n'.join(result))


import sys, bisect
tc = int(sys.stdin.readline())
for _ in range(tc):
	n = int(sys.stdin.readline())
	ans = 0
	cnt = 0
	while n:
		if cnt % 2 == 0:
			if n % 2 == 1:
				ans += 1
				n -= 1
			elif (n - n // 2) % 2 == 1 or n - n // 2 == 2:
				ans += n // 2
				n //= 2
			else:
				ans += 1
				n -= 1
		elif n % 2 == 1:
			n -= 1
		elif (n - n // 2) % 2 == 1 or n - n // 2 == 2:
			n //= 2
		else:
			n -= 1
		cnt += 1
	print(ans)


dp = [0] * 100001
for i in range(1, 100001):
	if i % 2 == 0:
		dp[i] = i - min(dp[i - 1], dp[i // 2])
	else:
		dp[i] = i - dp[i - 1]
l = []
for i in range(int(input())):
	n = int(input())
	ans = 0
	while n > 100000:
		if n % 2 != 0:
			ans += 1
			n -= 1
			if n % 4 != 0:
				n //= 2
			else:
				n -= 1
		elif n % 4 == 0:
			ans += 1
			n -= 2
		else:
			ans += n // 2
			n //= 2
			n -= 1
	l.append(ans + dp[n])
for i in l:
	print(i)


def main():
	return '\n'.join(map(turnInputToAnswerToString, (input() for _ in range(int(input())))))

def turnInputToAnswerToString(data):
	return str(Chanek_s_nCoins(int(data)))

def Chanek_s_nCoins(nCoins):
	if nCoins == 1:
		return 1
	if nCoins % 2:
		return 1 + loser_s_nCoins(nCoins - 1)
	return nCoins - loser_s_nCoins(nCoins)

def loser_s_nCoins(nCoins):
	if nCoins < 5:
		return 1
	nCoinsLeft = nCoins // 2
	if nCoinsLeft % 2:
		return 1 + loser_s_nCoins(nCoinsLeft - 1)
	return 2 + loser_s_nCoins(nCoinsLeft - 2)
print(main())


t = int(input())
a = []
dp = [0] + [1] + [0] * 99999
for i in range(2, 100001):
	if i % 2 == 1:
		dp[i] = i - dp[i - 1]
	elif i % 4 == 0 and i > 4:
		dp[i] = dp[i - 2] + 1
	else:
		dp[i] = dp[i // 2 - 1] + i // 2
for _ in range(t):
	n = int(input())
	ans = 0
	r = n
	while r > 100000:
		if r % 2 == 0:
			if r % 4 == 0:
				ans += 1
				r -= 2
			else:
				ans += r // 2
				r //= 2
				r -= 1
		else:
			r -= 1
			ans += 1
			if r % 4 != 0:
				r //= 2
			else:
				r -= 1
	ans += dp[r]
	a.append(ans)
for x in a:
	print(x)


from sys import stdin
input = stdin.readline

def solve(start):
	res = 0
	while start != 0:
		if start == 4:
			res += 3
			start = 0
			continue
		if start % 4 == 0:
			res += 1
			start -= 2
		else:
			res += start // 2
			start = start // 2 - 1
	return res
for _ in range(int(input())):
	start = int(input())
	print(solve(start) if start % 2 == 0 else start - solve(start - 1))


import sys
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	ans = 0
	c = 0
	while n != 0:
		if c == 0:
			if n % 4 == 0 and n > 8:
				n = n - 1
				ans += 1
			elif n % 2:
				n = n - 1
				ans += 1
			else:
				ans += n // 2
				n = n // 2
			c = 1
		else:
			if n % 4 == 0 and n > 8:
				n = n - 1
			elif n % 2:
				n = n - 1
			else:
				n = n // 2
			c = 0
	sys.stdout.write(str(ans) + '\n')


import sys
input = sys.stdin.readline
t = int(input())
pass
for case in range(t):
	gold = [0, 0]
	n = int(input())
	i = 0
	while n > 0:
		if n % 4 == 0 and n > 4:
			gold[i] += n // 2
			gold[1 - i] += 1
			n = n // 2 - 1
		elif n % 2 == 0:
			gold[i] += n // 2
			n = n // 2
		else:
			gold[i] += 1
			n -= 1
		i = (i + 1) % 2
	print(gold[0])


from collections import Counter
from math import inf
from sys import stdin
import collections
import os
import sys
from io import IOBase, BytesIO
from sys import stdin, stdout
from math import sqrt
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange

def main():
	for test in range(int(input())):
		c = 0
		n = int(input())
		f = 1
		while n != 0:
			if f == 1:
				f = 0
				if n % 2 == 0 and n // 2 % 2 or n == 4:
					c += n // 2
					n //= 2
				else:
					c += 1
					n -= 1
			else:
				f = 1
				if n % 2 == 0 and n // 2 % 2 or n == 4:
					n //= 2
				else:
					n -= 1
		print(c)
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
main()


from sys import stdin
input = stdin.readline

def game(n):
	p1 = 0
	while n != 0:
		if n == 4:
			p1 += 3
			n = 0
			break
		if n % 4 == 0:
			n -= 2
			p1 += 1
		else:
			p1 += n // 2
			n = n // 2 - 1
	return p1
t = int(input())
for u in range(t):
	n = int(input())
	print(game(n) if n % 2 == 0 else n - game(n - 1))


m = 10 ** 5
dp = [0] * (m + 1)
for i in range(1, m + 1):
	if i % 2 != 0:
		dp[i] = i - dp[i - 1]
	else:
		dp[i] = i - min(dp[i // 2], dp[i - 1])
T = int(input())
output = []
for _ in range(T):
	n = int(input())
	plus = 0
	while n > m:
		if n % 4 == 0:
			plus += 1
			n -= 2
		elif n % 2 != 0:
			plus += 1
			n -= 1
			if n % 4 == 0:
				n -= 1
			else:
				n = n // 2
		else:
			plus += n // 2
			n = n // 2
			n -= 1
	output.append(dp[n] + plus)
for x in output:
	print(x)


T = int(input())
dp = [0] * 100001
dp[1] = 1
for i in range(2, 100001):
	if i % 2 == 1:
		dp[i] = i - dp[i - 1]
	elif i % 4 == 0 and i > 4:
		dp[i] = 1 + dp[i - 2]
	else:
		dp[i] = i // 2 + dp[i // 2 - 1]
l = []
for _ in range(T):
	N = int(input())
	ans = 0
	while N > 100000:
		if N % 2 == 1:
			ans += 1
			N -= 1
			if N % 4 == 0:
				N -= 1
			else:
				N //= 2
		elif N % 4 == 0:
			ans += 1
			N -= 2
		else:
			ans += N // 2
			N //= 2
			N -= 1
	l.append(ans + dp[N])
for i in range(T):
	print(l[i])


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	chanek = 0
	flag = 1
	while n > 0:
		if n % 4 == 0 and n != 4:
			if flag:
				chanek += 1
				n -= 1
				flag = 0
			else:
				n -= 1
				flag = 1
		elif n % 2:
			if flag:
				chanek += 1
				n -= 1
				flag = 0
			else:
				n -= 1
				flag = 1
		elif flag:
			chanek += n // 2
			n //= 2
			flag = 0
		else:
			n //= 2
			flag = 1
	print(chanek)


from sys import stdin, stdout

def op(x):
	if x == 4:
		x = 2
	elif x == 3:
		x = 2
	elif x <= 2:
		x = x - 1
	elif x % 4 == 0:
		x -= 1
	elif x % 2 == 0:
		x //= 2
	return x

def prec(x):
	s = 0
	while x:
		if x == 4:
			x = 0
			s += 3
		elif x == 3:
			x = 0
			s += 2
		elif x <= 2:
			x = 0
			s += 1
		elif x % 4 == 0:
			s += 1
			x -= 2
		elif x % 2 == 0:
			s += x // 2
			x //= 2
			x -= 1
		else:
			s += 1
			x -= 1
			x = op(x)
	return s
a = int(input())
ok = [0] * a
for i in range(a):
	ok[i] = prec(int(stdin.readline()))
stdout.write('\n'.join(map(str, ok)))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = 0
	p = n
	if n % 2 == 1:
		n -= 1
	while n > 0:
		if n == 4:
			a += 3
			n = 0
			continue
		if n % 4 == 0:
			a += 1
			n -= 2
		else:
			a += n // 2
			n = n // 2 - 1
	print(a if p % 2 == 0 else p - a)


d = [0, 1, 1, 2, 3, 2] + [0] * 999995
for i in range(6, 1000001):
	if i & 1 or i % 4 == 0:
		d[i] = i - d[i - 1]
	else:
		d[i] = i - d[i // 2]
n = int(input())
w = []
for _ in range(n):
	w.append(int(input()))
for i in range(n):
	k = w[i]
	t = 0
	s = 0
	while k > 0:
		if k < 1000001:
			if t & 1:
				s += k - d[k]
			else:
				s += d[k]
			break
		elif k & 1 == 1 or k % 4 == 0:
			k -= 1
			if not t & 1:
				s += 1
		else:
			k = k // 2
			if not t & 1:
				s += k
		t += 1
	w[i] = str(s)
print('\n'.join(w))


import sys
n = int(sys.stdin.readline().strip())
for i in range(n):
	t = int(sys.stdin.readline().strip())
	ans = 0
	while t > 0:
		if t % 2 == 0 and (t == 4 or t % 4 != 0):
			ans += t // 2
			t //= 2
			if t % 2 == 0:
				t //= 2
			else:
				t -= 1
		else:
			ans += 1
			t -= 1
			if t % 2 == 0 and (t == 4 or t % 4 != 0):
				t //= 2
			else:
				t -= 1
	print(ans)


from sys import stdin
input = stdin.buffer.readline
for _ in range(int(input())):
	n = int(input())
	a = [0, 0]
	c = 0
	while n:
		if n > 8:
			if not n & 1 and n >> 1 & 1:
				a[c] += n >> 1
				n >>= 1
			else:
				a[c] += 1
				n -= 1
			c ^= 1
		else:
			if not n & 1:
				a[c] += n >> 1
				n >>= 1
			else:
				a[c] += 1
				n -= 1
			c ^= 1
	print(a[0])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import *
from operator import itemgetter, attrgetter
from decimal import *
import bisect
import math
import heapq as hq
MOD = 10 ** 9 + 7

def pow(a, b, m):
	ans = 1
	while b:
		if b & 1:
			ans = ans * a % m
		b //= 2
		a = a * a % m
	return ans
vis = []
graph = []

def dfs(v):
	if vis[v]:
		return 0
	vis[v] = True
	temp = 0
	for vv in graph[v]:
		temp += dfs(vv)
	return 1 + temp

def ispalindrome(s):
	if s[:] == s[::-1]:
		return 1
	return 0

def f(n):
	if n < 5:
		return max(1, n - 1)
	if n % 2 or n % 4 == 0:
		return n - f(n - 1)
	return n - f(n // 2)
for _ in range(int(input())):
	n = int(input())
	print(f(n))


input = __import__('sys').stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	while n > 0:
		if n % 2 == 0 and (n == 4 or n % 4 != 0):
			n = n // 2
			c = c + n
			if n % 2 == 0:
				n = n // 2
			else:
				n = n - 1
		else:
			c = c + 1
			n = n - 1
			if n % 2 == 0 and (n == 4 or n % 4 != 0):
				n = n // 2
			else:
				n = n - 1
	print(c)


from math import log2, floor
T = int(input())

def count_set_bits(num):
	return bin(num).count('1')

def solve(x):
	log_2 = floor(log2(x + 1))
	from_log_2 = x + 1 - 2 ** log_2
	from_log_2_index = from_log_2 // 2
	if 2 ** (log_2 - 2) <= 1:
		return log_2
	else:
		ans_from_log_2 = count_set_bits(from_log_2_index % 2 ** (log_2 - 2))
		return log_2 + ans_from_log_2
for i in range(T):
	n = int(input())
	if n == 1:
		print(1)
	elif n % 2 == 0:
		print(n + 1 - solve(n + 1))
	else:
		print(solve(n))


t = int(input())
toprint = []
for _ in range(t):
	n = int(input())
	ans = 0
	while n:
		if n % 4 == 2 or n == 4:
			ans += n // 2
			n = (n - 2) // 2
		elif n == 1:
			ans += 1
			n = 0
		elif n == 5:
			ans += 2
			n = 0
		elif n == 8:
			ans += 5
			n = 0
		elif n % 4 == 3:
			ans += 1
			n = (n - 1) // 2
		elif n % 4 == 1:
			ans += 2
			n = (n - 3) // 2
		elif n % 4 == 0:
			ans += n // 2
			n = (n - 4) // 2
	toprint.append(ans)
print('\n'.join(map(str, toprint)))


t = int(input())
output = []
for i in range(t):
	n = int(input())
	count = 0
	taken = 0
	ans = 0
	while n:
		if n % 2 == 0 and n // 2 % 2 == 1 or n == 4:
			n = n // 2
			taken = n
		else:
			n -= 1
			taken = 1
		count += 1
		if count % 2 == 1:
			ans += taken
	output.append(ans)
print('\n'.join(map(str, output)))


import sys
input = sys.stdin.readline

def get_coins(c):
	coins = 0
	if c % 2:
		coins += 1
		c -= 1
	elif c // 2 % 2 or c == 4:
		coins += c // 2
		c = c // 2
	else:
		coins += 1
		c -= 1
	return (c, coins)

def find_max_coins(c):
	max_coins = 0
	opponent = 0
	round = 1
	while c != 0:
		if round % 2:
			(c, coins) = get_coins(c)
			max_coins += coins
		else:
			(c, coins) = get_coins(c)
		round += 1
	return int(max_coins)
t = int(input())
for item in range(t):
	c = int(input().strip())
	print(find_max_coins(c))


from math import log2
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	c = 0
	k = 0
	while n > 4:
		if n % 2 == 0:
			if n // 2 % 2 == 0:
				n -= 1
				if k == 0:
					c += 1
					k = 1
				else:
					k = 0
			else:
				if k == 0:
					c += n // 2
					k = 1
				else:
					k = 0
				n //= 2
		if n % 2 == 1:
			if k == 0:
				c += 1
				k = 1
			else:
				k = 0
			n -= 1
	if n == 4:
		if k == 0:
			c += 3
		else:
			c += 1
	elif n == 3:
		if k == 0:
			c += 2
		else:
			c += 1
	elif n == 2:
		c += 1
	elif n == 1:
		if k == 0:
			c += 1
	stdout.write(str(c) + '\n')


output = []
for i in range(int(input())):
	n = int(input())
	(ans, flag) = (0, 1)
	while n:
		test = 0
		if n % 2 == 0 and n // 2 % 2 or n == 4:
			n //= 2
			test = n
		else:
			n -= 1
			test = 1
		if flag:
			ans += test
		flag ^= 1
	output.append(ans)
print('\n'.join(map(str, output)))