You are given an integer N. Find the number of distinct XORs it is possible to make using two positive integers no larger than N.

Formally, let S be the set
S = \{x\oplus y \mid 1 ≤ x, y ≤ N\}

where \oplus denotes the [bitwise XOR] operation. 

Find |S| (where |S| denotes the size of set S. Note that a set, by definition, has no repeated elements). The answer might be large, so output it modulo 10^{9} + 7.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, which contains one integer N.

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

For each test case, output a single line containing the answer, modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{12}$

----- Sample Input 1 ------ 
3
1
3
7
----- Sample Output 1 ------ 
1
4
8
----- explanation 1 ------ 
Test Case 1: $N = 1$, so the only XOR we can possibly make is $1 \oplus 1 = 0$. Thus, the answer is $1$.

Test Case 2: $N = 3$, which gives us $S = \{0, 1, 2, 3\}$ as the set of possible XORs. Thus, the answer is $|S| = 4$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n & n - 1 == 0:
		print((n * 2 - 1) % 1000000007)
	else:
		a = math.floor(math.log(n, 2))
		n = 2 ** (a + 1)
		print(n % 1000000007)


t = int(input())
for i in range(t):
	n = int(input())
	l = 1
	mod = 1000000000.0 + 7
	if n <= 2:
		print(n)
		continue
	i = 0
	j = 40
	while j > i:
		m = (i + j) // 2
		if 2 ** m <= n:
			l = m
			i = m + 1
		else:
			j = m
	l = 2 ** l % mod
	if l == n:
		l = l * 2 % mod
		l = l - 1
		print(int(l))
	else:
		print(int(2 * l % mod))


for _ in range(int(input())):
	z = int(input())
	x1 = 1
	rem = 10 ** 9 + 7
	if z <= 2:
		print(z)
		continue
	i = 0
	j = 40
	while j > i:
		r = (i + j) // 2
		if 2 ** r <= z:
			x1 = r
			i = r + 1
		else:
			j = r
	x1 = 2 ** x1 % rem
	if x1 == z:
		x1 = x1 * 2 % rem
		x1 = x1 - 1
		print(x1)
	else:
		print(2 * x1 % rem)


import math
T = int(input())
for t in range(0, T):
	N = int(input())
	ans = 0
	M = 1000000007
	if N == 1:
		ans = 1
	elif N == 2:
		ans = 2
	elif N & N - 1 == 0:
		ans = 2 * N - 1
	else:
		ans = pow(2, int(math.log(N, 2)) + 1)
	print(ans % M)


import math
t = int(input())
for zz in range(t):
	n = int(input())
	i = 1
	p = 0
	q = 0
	z = 0
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		while True:
			if 2 ** i > n and 2 ** (i - 1) < n:
				p = i
				break
			elif 2 ** i == n:
				q = i
				break
			i += 1
		if p > 0:
			print(2 ** p % (10 ** 9 + 7))
		elif q > 0:
			print(2 * n - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		for i in range(1, n):
			if n < 2 ** i:
				break
		if n == 2 ** (i - 1):
			ans = 2 * n - 1
			print(ans % 1000000007)
		else:
			ans = 2 ** i
			print(ans % 1000000007)


m = 1000000007
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(2)
		continue
	j = 2
	while n > j:
		j *= 2
	if j == n:
		print((j * 2 - 1) % m)
	else:
		print(j % m)


l = 10 ** 9 + 7
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n & n - 1 == 0:
		print((n * 2 - 1) % l)
	else:
		j = 2
		while j < n:
			j = j * 2
		print(j % l)


MOD = 10 ** 9 + 7

def solve():
	n = int(input())
	if n == 1:
		return print(1)
	if n == 2:
		return print(2)
	bit = 1
	while bit <= n:
		bit <<= 1
	if bit == n * 2:
		bit = bit - 1
	print(bit % MOD)
t = int(input())
for _ in range(t):
	solve()


import math
try:
	for _ in range(int(input())):
		n = int(input())
		if n == 1:
			print(1)
		elif n == 2:
			print(2)
		else:
			bits = int(math.log2(n))
			ans = pow(2, bits + 1)
			if n & n - 1 == 0:
				print((2 * n - 1) % (pow(10, 9) + 7))
			else:
				print(ans % (pow(10, 9) + 7))
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	digits = 0
	x = n
	while x != 0:
		x >>= 1
		digits += 1
	largest = (1 << digits) - 1
	check = 1 << digits - 1
	if check != n:
		largest += 1
	if n == 2:
		print(2)
	else:
		divider = pow(10, 9) + 7
		ans = largest % divider
		print(ans)


mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = int(input())
	print(n if n < 3 else pow(2, len(bin(n)) - 2, mod) if n & n - 1 else (2 * n - 1) % mod)


for _ in range(int(input())):
	n = int(input())
	mod = int(1000000000.0 + 7)
	if n == 1 or n == 2:
		print(n)
	else:
		ans = 1
		while ans < n:
			ans *= 2
		if n & n - 1 == 0:
			ans = ans * 2 - 1
		print(ans % mod)


for _ in range(int(input())):
	n = int(input())
	mod = int(1000000000.0 + 7)
	if n == 1 or n == 2:
		print(n)
	elif n & n - 1 == 0:
		print((2 * n - 1) % mod)
	else:
		print(2 ** len(bin(n)[2:]) % mod)


for _ in range(int(input())):
	n = int(input())
	mod = int(1000000000.0 + 7)
	if n == 1 or n == 2:
		print(n)
	else:
		binn = bin(n)[2:]
		ans = 2 ** len(binn) % mod
		if binn.count('1') == 1:
			ans -= 1
		print(ans % mod)


try:
	p = int(input())
	while p > 0:
		p = p - 1
		n = int(input())
		t = 0
		while pow(2, t) <= n:
			t = t + 1
		if n == 2:
			print(2)
		elif n == pow(2, t - 1):
			k = pow(2, t) - 1
			print(k % 1000000007)
		else:
			d = pow(2, t)
			print(d % 1000000007)
except Exception:
	pass


for i in range(int(input())):
	z = int(input())
	x = 1
	rem = 10 ** 9 + 7
	if z <= 2:
		print(z)
		continue
	a = 0
	b = 40
	while b > a:
		r = (a + b) // 2
		if 2 ** r <= z:
			x = r
			a = r + 1
		else:
			b = r
	x = 2 ** x % rem
	if x == z:
		x = x * 2 % rem
		x = x - 1
		print(x)
	else:
		print(2 * x % rem)


import numpy as np
T = int(input(''))
numlist1 = list()
for i in range(T):
	numlist1.append(int(input('')))
MOD = 10 ** 9 + 7
for nums in numlist1:
	numlist = range(1, nums)
	if nums == 2:
		print('2')
	elif np.log2(nums) - int(np.log2(nums)) == 0:
		print((int(2 ** (np.floor(np.log2(nums)) + 1)) - 1) % MOD)
	else:
		print(int(2 ** (np.floor(np.log2(nums)) + 1)) % MOD)


import sys
from math import log, log2, ceil

def solve():
	n = int(input())
	if n <= 2:
		print(n)
		return
	p = log2(n)
	if ceil(p) == p:
		print((n * 2 - 1) % (1000000000 + 7))
		return
	p = ceil(p)
	print(pow(2, p) % (1000000000 + 7))
for _ in range(int(input())):
	solve()


import math
mod = int(1000000000.0 + 7)
tests = int(input())
for testcases in range(tests):
	n = int(input())
	x = int(math.log2(n)) + 1
	ans = 2 ** x
	if math.log2(n) == int(math.log2(n)):
		ans -= 1
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		print(ans % mod)


import math
n = int(input())
k = 1000000007
for i in range(n):
	l = []
	n1 = int(input())
	n3 = int(n1)
	if n1 < 1:
		continue
	if n1 == 2:
		print(2)
	elif n1 & n1 - 1 == 0:
		print((2 * n3 - 1) % k)
	else:
		bit = math.log2(n1)
		ans = 2 ** (int(bit) + 1)
		print(ans % k)


t = int(input())
for _ in range(t):
	n = int(input())
	temp = n
	c = 0
	ans = 0
	mo = int(1000000000.0) + 7
	count = 0
	while n > 0:
		if n % 2 != 0:
			count += 1
		n //= 2
		c += 1
	for po in range(c):
		ans += 2 ** po
	ans = (ans + 1) % mo
	if temp == 2:
		ans = 2
	elif count == 1:
		ans = 2 * temp - 1
	print(ans % mo)


import math
M = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('1')
	elif n == 2:
		print('2')
	else:
		if n & n - 1 == 0:
			ans = int(2 * n - 1) % M
		else:
			bits = 1 + int(math.log2(n))
			ans = int(2 ** bits) % M
		print(ans)


def main():
	mod = 10 ** 9 + 7
	for _ in range(int(input())):
		n = int(input())
		if n <= 2:
			print(n)
		elif n & n - 1:
			print(pow(2, len(bin(n)) - 2, mod))
		else:
			print((2 * n - 1) % mod)
main()


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		flag = True
		length = 0
		while n > 1:
			if n % 2 == 1 and n != 2:
				flag = False
			n //= 2
			length += 1
		ans = int(math.pow(2, length + 1))
		if flag:
			print((ans - 1) % 1000000007)
		else:
			print(ans % 1000000007)


import math
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(n)
	elif n & n - 1 == 0:
		print(pow(2 * n - 1, 1, 10 ** 9 + 7))
	else:
		a = math.ceil(math.log2(n))
		print(pow(2 ** a, 1, 10 ** 9 + 7))


import math
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		if n & n - 1 == 0:
			ans = (2 * n - 1) % mod
		else:
			bit = int(math.log2(n))
			ans = int(math.pow(2, bit + 1)) % mod
		print(ans)


mod = 10 ** 9 + 7

def exp(x):
	n = 1
	base = 0
	while n < x:
		n *= 2
		base += 1
	return base

def power(x, n):
	ans = 1
	x = x % mod
	while n:
		if n & 1:
			ans = ans * x % mod
		n = n >> 1
		x = x * x % mod
	return ans
for u in range(int(input())):
	n = int(input())
	if n == 1 or n == 2:
		print(n)
	else:
		p = exp(n)
		if 2 ** p == n:
			ans = power(2, p + 1) - 1
		else:
			ans = power(2, p)
		print(ans)


import math
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n & n - 1 == 0:
		print((2 * n - 1) % 1000000007)
	else:
		a = math.floor(math.log2(n))
		n = 2 ** (a + 1)
		print(n % 1000000007)


import sys
import math

def isp(n):
	return math.ceil(math.log2(n)) == int(math.log2(n))

def pr(a, b):
	if b == 1:
		return a
	if b % 2:
		return a * pr(a * a, b // 2)
	else:
		return pr(a * a, b // 2)
input = sys.stdin.readline
t = int(input())
m = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	x = math.ceil(math.log2(n))
	if n == 2:
		print(2)
	elif isp(n):
		print((n * 2 - 1) % m)
	else:
		print(pr(2, x) % m)


import math
t = int(input())
for _ in range(t):
	num = int(input())
	if num <= 2:
		print(num)
	elif num & num - 1 == 0:
		print((num * 2 - 1) % 1000000007)
	else:
		power = int(math.log2(num))
		print(2 ** (power + 1) % 1000000007)


import math as m
t = int(input())
for z in range(t):
	n = int(input())
	cnt = 0
	a = n
	while 1:
		if a / 2 < 1:
			break
		else:
			a = a / 2
			cnt += 1
	if n == 1 or n == 2:
		print(2 ** cnt)
	elif n == 2 ** cnt:
		s = 2 ** (cnt + 1)
		print((s - 1) % (10 ** 9 + 7))
	else:
		s = 2 ** (cnt + 1)
		print(s % (10 ** 9 + 7))


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		tot = int(math.log(n, 2))
		if n & n - 1 != 0:
			print(2 ** (tot + 1) % (10 ** 9 + 7))
		else:
			print((2 ** (tot + 1) - 1) % (10 ** 9 + 7))


for _t in range(int(input())):
	n = int(input())
	ans = 1
	if n == 2:
		print('2')
		continue
	while ans < n:
		ans *= 2
	if n == ans:
		ans *= 2
		ans -= 1
	print(int(ans % (1000000000.0 + 7)))


from math import log
a = int(input())
mod = 1000000007
for i in range(a):
	b = int(input())
	if b == 2:
		print(2)
	elif b & b - 1 == 0:
		print((2 * b - 1) % mod)
	else:
		print(2 ** int(log(b, 2) + 1) % mod)


for _ in range(int(input())):
	n = int(input())
	b = bin(n).replace('0b', '')
	l = len(b)
	if n == 2:
		print(2)
	elif n == 2 ** (l - 1) and n <= 10 ** 12:
		print((2 ** l - 1) % (10 ** 9 + 7))
	else:
		print(2 ** l % (10 ** 9 + 7))


import numpy as np
CONST = 1000000007
T = int(input(''))
numlist1 = list()
for i in range(T):
	numlist1.append(int(input('')))
for nums in numlist1:
	numlist = range(1, nums)
	if nums == 2:
		print('2')
	elif np.log2(nums) - int(np.log2(nums)) == 0:
		print((int(2 ** (np.floor(np.log2(nums)) + 1)) - 1) % CONST)
	else:
		print(int(2 ** (np.floor(np.log2(nums)) + 1)) % CONST)


import math
for i in range(int(input())):
	n = int(input())
	a = len(bin(n).replace('0b', ''))
	m = 10 ** 9 + 7
	if n == 1 or n == 2:
		print(n)
	else:
		b = math.log(n, 2)
		if math.floor(b) == math.ceil(b):
			ans = 2 ** a - 1
		else:
			ans = 2 ** a
		print(ans % m)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(2)
		continue
	if n & n + 1 == 0:
		print((n + 1) % mod)
	elif n & n - 1 == 0:
		print((n * 2 - 1) % mod)
	else:
		print(int('1' + '0' * len(bin(n)[2:]), 2) % mod)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	mod = 1000000007
	if n == 2:
		print(2)
		continue
	elif n == 1:
		print(1)
		continue
	x = math.log2(n)
	if x - int(x) == 0:
		print((2 ** (int(x) + 1) - 1) % mod)
		continue
	x = math.ceil(x)
	print(2 ** x % mod)


from typing import DefaultDict
from math import sqrt
from collections import OrderedDict, defaultdict
import math

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l
for _ in range(int(input())):
	bool = True
	flag = True
	n = int(input())
	mod = 10 ** 9 + 7
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n == 3:
		print(4)
	else:
		s = bin(n)[2:]
		if s.count('1') == 1:
			print((n * 2 - 1) % mod)
		else:
			print(2 ** len(s) % mod)


import math

def Log2(x):
	return math.log10(x) / math.log10(2)

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for t in range(int(input())):
	n = int(input())
	if n == 2:
		print('2')
	elif isPowerOfTwo(n):
		print((2 * n - 1) % 1000000007)
	else:
		print(highestPowerof2(n) * 2 % 1000000007)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
p = 10 ** 9 + 7
while t:
	t -= 1
	n = inp()
	if n <= 2:
		print(n)
	else:
		x = bin(n)[2:]
		res = pow(2, len(x), p)
		if x.count('1') == 1:
			res -= 1
		print(res % p)


T = int(input())
for _ in range(T):
	n = int(input())
	if n == 1 or n == 2:
		print(n)
	else:
		i = 2
		while i <= n:
			if 2 ** i == n:
				print((2 ** (i + 1) - 1) % 1000000007)
				break
			elif 2 ** i > n:
				print(2 ** i % 1000000007)
				break
			else:
				i += 1


from sys import stdin, stdout, maxsize
import math
import heapq
from collections import defaultdict
ii = lambda : int(input())
di = lambda : defaultdict(lambda : 0)
dl = lambda : defaultdict(lambda : list())
li = lambda : list(map(int, stdin.readline().strip().split()))
mi = lambda : stdin.readline().strip().split()
si = lambda : stdin.readline().strip()
arr = [4]
limi = 10 ** 12
modd = 10 ** 9 + 7
while arr[-1] <= limi:
	arr.append(arr[-1] * 2)
for _ in range(ii()):
	a = ii()
	if a == 1:
		print(1)
		continue
	res = 0
	if a == 2:
		print(2)
		continue
	if a in arr:
		res = 1
	for i in arr:
		if i > a:
			print((i - res) % modd)
			break


import math
for i in range(int(input())):
	n = int(input())
	mod = 1000000000.0 + 7
	if n == 2:
		print(2)
		continue
	if n & n - 1 == 0:
		print(int((2 * n - 1) % mod))
	else:
		a = int(math.log(n, 2))
		ans = pow(2, a + 1)
		print(int(ans % mod))


import math
T = int(input())
for i in range(T):
	N = int(input())
	if N == 1:
		z = 1
	elif N == 2:
		z = 2
	elif N == 3:
		z = 4
	elif N == 4:
		z = 7
	elif math.log(N, 2) % 1 == 0:
		z = 2 * N - 1
	else:
		a = math.log(N, 2)
		z = pow(2, int(a) + 1)
	num = pow(10, 9) + 7
	print(z % num)


import math
for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(2)
	else:
		f = math.floor(math.log(n, 2)) == math.ceil(math.log(n, 2))
		if f:
			print((int(math.pow(2, int(math.log(n, 2)) + 1)) - 1) % (10 ** 9 + 7))
		else:
			print(int(math.pow(2, int(math.log(n, 2)) + 1)) % (10 ** 9 + 7))


from sys import stdin, stdout
t = int(stdin.readline())
for i in range(t):
	n = int(stdin.readline())
	my_dict = {1: 1, 2: 2, 3: 4, 4: 7}
	if n in my_dict:
		print(my_dict[n])
	else:
		m = 2
		while 1 << m < n:
			m += 1
		if 1 << m == n:
			print(((1 << m + 1) - 1) % (10 ** 9 + 7))
		else:
			print((1 << m) % (10 ** 9 + 7))


def setbits(a):
	c = 0
	while a > 0:
		c += 1
		a &= a - 1
	return c
for tc in range(int(input())):
	n = int(input())
	mod = 1000000007
	if n <= 3:
		if n == 1:
			print(1)
		elif n == 2:
			print(2)
		elif n == 3:
			print(4)
	else:
		most = 0
		for r in range(1, 60):
			if n >> r & 1 == 1:
				most = max(most, r)
		r = 1 << most
		if setbits(n) == 1:
			print((2 * r - 1) % mod)
		else:
			print(2 * r % mod)


import math
T = int(input())
while T:
	num = int(input())
	if num == 1:
		print(1)
	elif num == 2:
		print(2)
	elif num & num - 1 == 0:
		print((2 * num - 1) % 1000000007)
	else:
		hodg = math.floor(math.log(num, 2))
		ans = pow(2, hodg + 1) % 1000000007
		print(ans)
	T -= 1


import math

def solve(n, M):
	if n == 1:
		return 1
	elif n == 2:
		return 2
	elif n == 3:
		return 4
	elif n == 4:
		return 7
	else:
		l = math.floor(math.log(n, 2))
		l += 1
		if 2 ** (l - 1) != n:
			ans = 2 ** l
		else:
			ans = 2 ** l - 1
		ans %= M
		return ans
for _ in range(int(input())):
	n = int(input())
	a = solve(n, 10 ** 9 + 7)
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	dig = 0
	ones = 0
	while n:
		if n & 1 == 1:
			ones += 1
		dig += 1
		n = n // 2
	sol = 2 ** dig % 1000000007
	if ones == 1:
		sol -= 1
		if dig == 2:
			sol -= 1
	print(sol)


def nextPowerOf2(n):
	count = 0
	if n and (not n & n - 1):
		return n
	while n != 0:
		n >>= 1
		count += 1
	return 1 << count
t = int(input())
for i in range(t):
	modulo = 10 ** 9 + 7
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		x = nextPowerOf2(n)
		if x == n:
			print((x * 2 - 1) % modulo)
		else:
			print(x % modulo)


def bin_exp(n, p):
	mod = int(10 ** 9) + 7
	pwrs = [n]
	for i in range(60):
		pwrs.append(pwrs[-1] * pwrs[-1] % mod)
	i = 0
	prod = 1
	while p:
		if p & 1 == 1:
			prod = prod * pwrs[i] % mod
		i += 1
		p = p // 2
	return prod
t = int(input())
for _ in range(t):
	n = int(input())
	dig = 0
	ones = 0
	while n:
		if n & 1 == 1:
			ones += 1
		dig += 1
		n = n // 2
	sol = bin_exp(2, dig)
	if ones == 1:
		sol -= 1
		if dig == 2:
			sol -= 1
	print(sol)


M = 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	num = len(bin(n)) - 2
	if n <= 2:
		print(n)
	elif bin(n).count('1') == 1:
		print((2 ** num - 1) % M)
	else:
		print(2 ** num % M)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 2:
		print(n)
	else:
		s = bin(n)
		num = len(s) - 2
		out = pow(2, num, M)
		if s.count('1') == 1:
			out -= 1
		print(out % M)


modu = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(n)
	else:
		c = bin(n)[2:]
		d = pow(2, len(c), modu)
		if c.count('1') == 1:
			d -= 1
		print(d % modu)


def nextPowerOf2(n):
	count = 0
	if n and (not n & n - 1):
		return n
	while n != 0:
		n >>= 1
		count += 1
	return 1 << count
for _ in range(int(input())):
	n = int(input())
	if n == 1 or n == 2:
		print(n)
	elif n & n - 1 == 0:
		print((2 * n - 1) % (10 ** 9 + 7))
	else:
		print(nextPowerOf2(n + 1) % (10 ** 9 + 7))


from collections import deque
from math import *
import sys
import random
from bisect import *
from collections import deque
from math import *
import sys
import random
from bisect import *

def nxt(v):
	v |= v >> 1
	v |= v >> 2
	v |= v >> 4
	v |= v >> 8
	v |= v >> 16
	v = v ^ v >> 1
	return v
nxt = lambda x: pow(2, ceil(log(x) / log(2)))

def diku(n):
	mod = 10 ** 9 + 7
	if n & n - 1 == 0:
		return (2 * (n % mod) - 1) % mod
	else:
		return int(nxt(n)) % mod
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(n)
	else:
		print(diku(n))


from math import log2, pow
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(2)
		continue
	s = pow(2, len(bin(n)) - 2)
	s = s % (10 ** 9 + 7)
	if n & n - 1 == 0:
		print(int(s) - 1)
		continue
	print(int(s))


for jkfd in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print(2)
		continue
	elif n == 3:
		print(4)
		continue
	p = False
	x = 4
	asdf = [2 ** i for i in range(2, 100)]
	if n in asdf:
		p = True
	while x < n:
		if x == n:
			p = True
		x *= 2
	n = bin(n)[2:]
	if p:
		ans = 2 ** len(n) - 1
	else:
		ans = 2 ** len(n)
	print(ans % 1000000007)


try:
	import math
	test_cases = int(input())
	for i in range(0, test_cases):
		N = int(input())
		if N == 1:
			print(1)
			continue
		if N == 2:
			print(2)
			continue
		s = pow(2, len(bin(N)) - 2)
		s = s % 1000000007
		if math.log(N, 2) == int(math.log(N, 2)):
			print(s - 1)
			continue
		print(s)
except:
	pass


try:
	for _ in range(int(input())):
		z = int(input())
		x1 = 1
		rem = 10 ** 9 + 7
		if z <= 2:
			print(z)
			continue
		i = 0
		j = 40
		while j > i:
			r = (i + j) // 2
			if 2 ** r <= z:
				x1 = r
				i = r + 1
			else:
				j = r
		x1 = 2 ** x1 % rem
		if x1 == z:
			x1 = x1 * 2 % rem
			x1 = x1 - 1
			print(x1)
		else:
			print(2 * x1 % rem)
except Exception as e:
	pass


for _ in range(int(input())):
	N = int(input())
	l = 1
	mod = 1000000000.0 + 7
	if N <= 2:
		print(N)
		continue
	i = 0
	j = 40
	while j > i:
		m = (i + j) // 2
		if 2 ** m <= N:
			l = m
			i = m + 1
		else:
			j = m
	l = 2 ** l % mod
	if l == N:
		l = l * 2 % mod
		l = l - 1
		print(int(l))
	else:
		print(int(2 * l % mod))


from math import log2, ceil

def solve(n):
	mod = int(1000000000.0) + 7
	dp = [0, 1, 2, 4]
	res = 0
	if n <= 3:
		res = dp[n]
	else:
		bits = ceil(log2(n))
		if n == pow(2, bits):
			res = pow(2, bits + 1, mod) - 1
		else:
			res = pow(2, bits, mod)
	return res
t = int(input())
for _ in range(t):
	N = int(input())
	print(solve(N))