As punishment for attacking Sunland, Wet Shark is now forced to walk on a line of numbered squares, starting from $\mbox{1}$ and going to infinity. Wet Shark initially has a strength of $\mbox{S}$. To make the experience harder for Wet Shark, each square that has a label divisible by $\begin{array}{c}4\end{array}$ and/or $2$ but not divisible by $\textbf{42}$ contains a black glob of jelly, stepping on which his strength decreases by $\mbox{1}$. 

Wet Shark does not know that this line of squares is infinitely long, and he is determined to continue walking until his strength reaches $\mbox{0}$. Wet Shark walks from square to square, so he starts at square $\mbox{1}$, goes to square $2$, then $3$, then $\begin{array}{c}4\end{array}$, etc. 

Wet Shark’s punisher needs your help, and wants to compute where Wet Shark will stop in order to meet him there and punish him. Given Wet Shark’s initial strength $\mbox{S}$, find the square on which Wet Shark’s strength will reach $\mbox{0}$. Wet Shark can go far if defenses are not strong enough, so please output the answer modulo $10^9+7$. Wet Shark is curious, so he wants to know that given $\mbox{S}$ strength initially, how far he will go for different values $\mbox{S}$. Help him figure out how long he can go without doom for each $\mbox{S}$.

Input Format

The first line of the input contains an integer $\mathbf{T}$, the number of queries. The following lines describe the queries.

Each query consists of a line containing a single integer, which is the value of $\mbox{S}$.

Output Format

Print $\mathbf{T}$ lines, each line containing the answer for each query, i.e. the last square Wet Shark will reach before he runs out of strength, starting with a strength of $\mbox{S}$, modulo $10^9+7$.

Constraints  

$1\leq T\leq100$ 

$1\leq S\leq10^{18}$  

Sample Input
2
3
4

Sample Output
6 
8

Explanation

Square 1: 3 strength 

Square 2: 2 strength 

Square 3: 2 strength 

Square 4: 1 strength 

Square 5: 1 strength 

Square 6: 0 strength  

Thus the answer is 6.

Difficulty: EASY
Tags: Matrices

Starter code:

Solutions:
def calc(x):
	MOD = 10 ** 9 + 7
	twenties = x // 20
	rem = x % 20
	if rem == 0:
		return (42 * twenties - 2) % MOD
	else:
		return (42 * twenties + 2 * rem) % MOD
tcs = int(input())
for i in range(tcs):
	print(calc(int(input())))


P = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	n -= 1
	print((2 + n // 20 * 42 + n % 20 * 2) % P)


import sys
from math import sqrt

def solve():
	stdin = sys.stdin
	write = sys.stdout.write
	t = int(stdin.readline())
	for _ in range(t):
		s = int(stdin.readline())
		lb = 0
		ub = s * 4
		while ub - lb:
			mid = (ub + lb) // 2
			t = mid // 2 - mid // 42
			if t < s:
				lb = mid + 1
			else:
				ub = mid
		print(lb % (10 ** 9 + 7))
solve()


n = int(input())
for i in range(n):
	a = int(input())
	b = (a - 1) % 20 + 1
	c = (a - b) // 10
	print(int((2 * a + c) % 1000000007))


num_test_cases = int(input())
LARGE_MOD = 10 ** 9 + 7
for c in range(num_test_cases):
	S = int(input())
	k = (S - 1) // 20
	r = (S - 1) % 20 + 1
	print((42 * k + 2 * r) % LARGE_MOD)


import math
t = int(input())
for i in range(0, t):
	s = int(input())
	if s % 20 == 0:
		ans = (42 * (s // 20) - 2) % 1000000007
	else:
		ans = (42 * (s // 20) + 2 * (s % 20)) % 1000000007
	print(ans)


from math import ceil

def f(value, n):
	current_step = 2 * n
	prev2_step = 2 * n - 2
	count_cur = current_step // 2 - current_step // 42
	count_prev = prev2_step // 2 - prev2_step // 42
	if count_cur > value or (count_cur == value and count_prev == value):
		return -1
	elif count_cur == value:
		return 0
	else:
		return 1

def bin_search(array, low, high, cond):
	if low > high:
		return None
	mid = (low + high) // 2
	res = cond(array, mid)
	if res == -1:
		return bin_search(array, low, mid - 1, cond)
	elif res == 0:
		return mid
	else:
		return bin_search(array, mid + 1, high, cond)

def my_func(strength):
	square = 2 * bin_search(strength, strength, 2 * strength, f)
	return square
modulo = 10 ** 9 + 7
for t in range(int(input())):
	strength = int(input())
	print(my_func(strength) % modulo)


t = int(input())
N = 42
for _ in range(t):
	s = int(input())
	x = 2 * s
	d = x // N
	new_x = x + 2 * d
	new_d = new_x // N
	while new_d > d:
		new_x = x + 2 * new_d
		d = new_d
		new_d = new_x // N
	print(new_x % (10 ** 9 + 7))


T = int(input())
for t in range(T):
	S = int(input())
	r = S % 20
	if r == 0:
		r = 20
	x = 2 * (S + int((S - r) // 20)) % 1000000007
	print(x)


t = int(input())
for i in range(t):
	s = int(input())
	count = 0
	while s != 0:
		temp = 0
		old_count = count
		count += 2 * s
		temp1 = old_count + 42 - old_count % 42
		temp2 = count - count % 42
		if temp2 == count:
			temp2 -= 42
		if temp2 >= temp1:
			temp += (temp2 - temp1) // 42 + 1
		if count % 42 == 0:
			count += 2
		s = temp
	print(count % 1000000007)


T = int(input())
for _ in range(T):
	S = int(input())
	mod = int(1000000000.0 + 7)
	P = S // 20
	Q = S % 20
	result = (42 * P + 2 * Q) % mod
	if P > 0 and Q == 0:
		result -= 2
	print(result)


for a in range(int(input())):
	strn = int(input())
	res = 0
	res = strn // 20 * 42
	strn = strn % 20
	if strn == 0:
		res = res - 1
	while strn > 0:
		if res % 2 == 0 and res % 42 != 0:
			strn -= 1
		res += 1
	print((res - 1) % (10 ** 9 + 7))


M = 10 ** 9 + 7
for _ in range(int(input())):
	S = int(input())
	if S % 20 == 0:
		print((42 * (S // 20) - 2) % M)
	else:
		print((42 * (S // 20) + S % 20 * 2) % M)


import math
import time

def get_num_steps(s):
	s1 = s // 20
	s2 = s - s1 * 20
	num_steps = s1 * 42
	if s2 == 0:
		num_steps -= 2
	else:
		while s2 > 0:
			num_steps += 1
			if (num_steps % 2 == 0 or num_steps % 4 == 0) and num_steps % 42 != 0:
				s2 = s2 - 1
	return num_steps
t = int(input())
for i in range(0, t):
	s_i = int(input())
	op = get_num_steps(s_i) % 1000000007
	print(op)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


from math import floor
M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = int(input())
	res = 0
	if s % 20 == 0:
		res = 42 * (s // 20) - 2
	else:
		res = 42 * (s // 20) + 2 * (s % 20)
	print(res % M)


t = int(input())
for j in range(t):
	s = int(input())
	(q, temp) = (0, s)
	while s >= 21:
		q += s // 21
		s = s // 21 + s % 21
	print((temp + q) * 2 % 1000000007)


from math import log
M = 10 ** 9 + 7
for _ in range(int(input())):
	S = int(input())
	a = 2 * S
	b = 2 * (a // 42)
	while b > 0:
		c = a // 42
		a += b
		a += 2 * (a // 42 - c - b // 42)
		b = 2 * (b // 42)
	if a % 42 == 0:
		a += 2
	print(a % M)


for _ in range(int(input())):
	s = int(input())
	answer = 2 * (21 * s // 20)
	if s % 20 == 0:
		answer -= 2
	print(answer % 1000000007)


T = int(input())
for _ in range(T):
	S = int(input())
	result = 2 * S + ((S - 1) // 10 - (S - 1) // 10 % 2)
	print(result % (10 ** 9 + 7))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


n = int(input())
mod = 1000000007
for _ in range(n):
	s = int(input())
	n = 2 * s // 42
	while n != 2 * (s + n) // 42:
		n = 2 * (s + n) // 42
	print(2 * (s + n) % mod)


t = int(input())
for i in range(t):
	s = int(input())
	if s % 20 == 0:
		sq = s // 20 * 42 - 2
	else:
		sq = s // 20 * 42 + s % 20 * 2
	print(sq % (pow(10, 9) + 7))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


MODINV = 23809524
MOD = 1000000007

def solve():
	N = int(input())
	lo = int(1)
	hi = int(10000000000000000000)
	while lo < hi:
		mid = (lo + hi) // 2
		y = N - mid // 2 + mid // 42
		if y > 0:
			lo = mid + 1
		else:
			hi = mid
	print(lo % MOD)

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


T = int(input().strip())
for i in range(0, T):
	S = int(input().strip())
	modulo = 10 ** 9 + 7
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % modulo)


T = int(input())
for _ in range(T):
	x = int(input()) * 2
	if x >= 21:
		temp1 = x // 42
		x += temp1 * 2
		temp2 = x // 42
		while temp1 < temp2:
			x += (temp2 - temp1) * 2
			temp1 = temp2
			temp2 = x // 42
	print(x % 1000000007)


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


modulo = 1000000007
for _ in range(int(input().strip())):
	s = int(input().strip())
	print((s // 20 * 42 % modulo + (-2 if s % 20 == 0 else s % 20 * 2)) % modulo)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


for _ in range(int(input().strip())):
	s = int(input().strip())
	print(2 * (s + s // 20 - (s % 20 == 0)) % (10 ** 9 + 7))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


for _ in range(int(input())):
	S = int(input())
	mod = 10 ** 9 + 7
	blocks = S // 20
	rem = S % 20
	if S % 20 == 0:
		steps = 42 * blocks - 2
	else:
		steps = 42 * blocks
	print(int((steps + 2 * rem) % mod))


def read_int():
	return int(input().strip())

def compute_sol(strength):
	n42 = strength // 20
	r42 = strength % 20
	sol = n42 * 42
	if r42 == 0:
		sol -= 2
	else:
		rem = strength - n42 * 20
		sol += rem * 2
	return sol
MODULUS = 10 ** 9 + 7
T = read_int()
for t in range(T):
	S = read_int()
	num_sol = compute_sol(S) % MODULUS
	print(num_sol)


import sys

def solve(s):

	def get_count(v):
		return v // 2 - v // 42
	(v1, v2) = (s * 2, s * 4)
	while v2 - v1 > 1:
		v = (v1 + v2) // 2
		cnt = get_count(v)
		if cnt < s:
			(v1, v2) = (v, v2)
		else:
			(v1, v2) = (v1, v)
	if get_count(v1) == s:
		return v1
	return v2
m = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	s = int(input())
	print(solve(s) % m)


for _ in range(int(input())):
	s = int(input())
	r = 2 * s // 42
	while 2 * (s + r) // 42 != r:
		r = 2 * (s + r) // 42
	print(2 * (s + r) % (10 ** 9 + 7))


T = int(input().strip())
for t in range(T):
	S = int(input().strip()) * 2
	a = S // 42
	S += a * 2
	b = S // 42
	while a < b:
		S += (b - a) * 2
		a = b
		b = S // 42
	print(S % 1000000007)


print('\n'.join(map(lambda x: str(((x - 1) // 20 + x) * 2 % (10 ** 9 + 7)), (int(input()) for _ in range(int(input()))))))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


def f(n):
	return n

def g(n, k):
	return f(n // k)

def f42(n):
	return g(n, 2) - g(n, 42)

def find(n):
	lo = 0
	hi = 10 ** 30
	while lo != hi:
		mid = (lo + hi) // 2
		if f42(mid) < n:
			lo = mid + 1
		else:
			hi = mid
	return lo % (10 ** 9 + 7)
for _ in range(int(input())):
	print(find(int(input())))


def wetshark(n):
	return (2 * n + 2 * ((n - 1) // 20)) % (10 ** 9 + 7)
out = []
T = int(input())
for t in range(T):
	out.append(wetshark(int(input())))
for o in out:
	print(o)


t = int(input())
for i in range(t):
	k = int(input())
	print(2 * (k + (k - 1) // 20) % 1000000007)


import sys
lines = sys.stdin.readlines()
for line in lines[1:]:
	s = int(line)
	q = s // 20
	r = s % 20
	if not r:
		m = 2
	else:
		m = 0
	print((q * 42 + r * 2 - m) % (10 ** 9 + 7))


import sys
t = int(input())
a = []
for x in range(t):
	a.append(int(input()))
for x in a:
	y = x * 2
	temp1 = y // 42
	y += temp1 * 2
	temp2 = y // 42
	while temp1 < temp2:
		y += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = y // 42
	print(y % 1000000007)


def fourtytwosinrange(start, range):
	return (start % 42 + range) // 42
for i in range(int(input())):
	strength = int(input())
	field = 0
	while strength:
		(a, b) = (field, strength * 2)
		field += b
		strength = fourtytwosinrange(a, b)
	print(field % (10 ** 9 + 7))


M = 10 ** 9 + 7
T = int(input())
for t in range(T):
	S = int(input())
	print((S // 20 * 2 + S * 2) % M if S % 20 else ((S // 20 - 1) * 2 + S * 2) % M)


N = int(input().strip())
K = 1000 * 1000 * 1000 + 7
for dummyN in range(N):
	S = int(input().strip())
	n42 = S // 20
	if S % 20 > 0:
		print((n42 * 42 + 2 * (S % 20)) % K)
	else:
		print((n42 * 42 - 2) % K)


t = int(input())
for i in range(t):
	s = int(input())
	if s < 21:
		steps = s * 2
	else:
		steps = (s - 21) // 20 * 42 + 44 + (s - 21) % 20 * 2
	print(steps % (10 ** 9 + 7))


from math import *
N = int(input())
MOD = 10 ** 9 + 7
for tc in range(N):
	s = int(input())
	start = 42 * ((s - 1) // 20)
	additional = 2 * ((s - 1) % 20 + 1)
	answer = start + additional
	print(answer % MOD)


def brutal(s):
	i = 1
	while True:
		if i % 2 == 0 and i % 42 != 0:
			s -= 1
		if s == 0:
			break
		i += 1
	return i

def result(s):
	r = s % 20
	d = s // 20 - 1
	return d * 42 + brutal(r + 20)
T = int(input())
for i in range(T):
	S = int(input())
	print(result(S) % (10 ** 9 + 7))


for i in range(int(input())):
	S = int(input())
	if S % 20 == 0:
		w = S // 20 * 42 - 2
	else:
		w = S // 20 * 42 + S % 20 * 2
	print(w % (10 ** 9 + 7))


t = int(input())
while t > 0:
	t -= 1
	s = int(input())
	print(2 * (s + (s - 1) // 20) % 1000000007)


import math
t = int(input().strip())
MOD_MASK = pow(10, 9) + 7
for _iter in range(t):
	N = int(input().strip())
	k = 21 * N // 20
	if k % 21 == 0:
		k -= 1
	print('{}'.format(2 * k % MOD_MASK))


num_probs = int(input())
m = 1000000007
for prob in range(num_probs):
	s = int(input())
	n1 = s // 20
	n2 = s % 20
	if n2 == 0:
		n1 -= 1
		n2 = 20
	print((42 * n1 + 2 * n2) % m)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	s = int(input())
	(x, y) = divmod(s, 20)
	if y == 0:
		print((42 * x - 2) % mod)
	else:
		print((42 * x + 2 * y) % mod)


T = int(input())
for _ in range(T):
	S = int(input())
	n42s = S // 20
	S -= n42s * 20
	if S == 0:
		n2s = -1
	else:
		n2s = S
	print((n42s * 42 + n2s * 2) % (10 ** 9 + 7))


T = int(input())
for i in range(T):
	S = int(input())
	d = S // 20
	m = S % 20
	if d == 0 and m == 0:
		print(1)
		continue
	if m == 0:
		print((42 * d - 2) % 1000000007)
	else:
		print((42 * d + m * 2) % 1000000007)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = n // 20
	if n % 20 == 0:
		a = a - 1
	x = int(2 * (n + a))
	print(x % 1000000007)


t = int(input())
while t > 0:
	s = int(input())
	q = s // 20
	r = s % 20
	ans = q * 42 + r * 2
	if r == 0:
		ans -= 2
	print(ans % (10 ** 9 + 7))
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	s = int(input())
	if s < 21:
		print(2 * s)
	else:
		high = s + s // 10
		low = s
		while high - low > 1:
			mid = (high + low) // 2
			tmp = mid - mid // 21
			if tmp >= s:
				high = mid
			else:
				low = mid
		print(2 * high % (10 ** 9 + 7))


m = 10 ** 9 + 7
T = int(input())
for t in range(T):
	S = int(input())
	a = 0
	b = S
	while b // 21 > a // 21:
		(a, b) = (b, b + b // 21 - a // 21)
	print(2 * b % m)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


for i in range(int(input())):
	s = int(input())
	modulo = pow(10, 9) + 7
	start = s
	end = s + s // 21
	while start // 21 != end // 21:
		(start, end) = (end, end + end // 21 - start // 21)
	print(2 * end % modulo)


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	S = int(input())
	(n, r) = divmod(S, 20)
	d = 42 * n + 2 * r
	if r == 0:
		d -= 2
	print(d % MOD)


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


nt = int(input())
for _ in range(nt):
	s = int(input())
	(q, r) = divmod(s, 20)
	square = 42 * q + 2 * r if r else 42 * q - 2
	print(square % 1000000007)


T = int(input())
for _ in range(T):
	x = 2 * int(input())
	temp1 = x // 42
	x = x + 2 * temp1
	temp2 = x // 42
	while temp1 < temp2:
		x = x + 2 * (temp2 - temp1)
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


from math import ceil
for _ in range(int(input())):
	s = int(input())
	stop = 0
	start = 0
	while s > 0:
		start = stop
		stop += 2 * s
		s = stop // 42 - start // 42
	print(stop % (10 ** 9 + 7))


def calc(s):
	q = (s - 1) // 20
	r = s % 20
	if r == 0:
		ans = q * 42 + 40
	else:
		ans = q * 42 + 2 * r
	return ans % 1000000007
T = int(input())
for i in range(T):
	S = int(input())
	print(calc(S))


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


for _ in range(int(input())):
	n = int(input())
	result = (n * 2 + (n - 1) // 20 * 2) % 1000000007
	print(result)


T = int(input())
for case in range(T):
	S = int(input())
	total = S // 20 * 42 + S % 20 * 2
	if S % 20 == 0:
		total -= 2
	print(total % 1000000007)


for _ in range(int(input())):
	x = int(input()) * 2
	y = x // 42
	x += y * 2
	z = x // 42
	while y < z:
		x += (z - y) * 2
		y = z
		z = x // 42
	print(x % 1000000007)


for _ in range(int(input())):
	x = int(input()) * 2
	temp1 = x // 42
	x += temp1 * 2
	temp2 = x // 42
	while temp1 < temp2:
		x += (temp2 - temp1) * 2
		temp1 = temp2
		temp2 = x // 42
	print(x % 1000000007)


def sum_2(n):
	return (n * 21 - 1) // 20 * 2
for _ in range(int(input())):
	n = int(input())
	print(sum_2(n) % 1000000007)


def calc(x):
	MOD = 10 ** 9 + 7
	twenties = x // 20
	rem = x % 20
	if rem == 0:
		return (42 * twenties - 2) % MOD
	else:
		return (42 * twenties + 2 * rem) % MOD
tcs = int(input())
for i in range(tcs):
	print(calc(int(input())))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	S = int(sys.stdin.readline())
	n = 2 * S // 42
	while 2 * (S + n) // 42 != n:
		n = 2 * (S + n) // 42
	print(2 * (S + n) % MOD)


for _ in range(int(input())):
	x = int(input()) * 2
	y = x // 42
	x += y * 2
	z = x // 42
	while y < z:
		x += (z - y) * 2
		y = z
		z = x // 42
	print(x % 1000000007)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = int(input())
	(low, high) = (0, 10 ** 20)
	while low <= high:
		cur = (low + high) // 2
		x = cur // 2 - cur // 42
		if x > s:
			high = cur - 1
		if x < s:
			low = cur + 1
		if x == s:
			break
	while (cur - 1) // 2 - (cur - 1) // 42 == s:
		cur -= 1
	print(cur % M)


P = 10 ** 9 + 7
for _ in range(int(input())):
	s = int(input())
	(q, r) = divmod(s - 1, 20)
	print((q * 42 + 2 * (r + 1)) % P)


import os
import sys

def y(s):
	s = s * 2
	x = s // 42
	s += x * 2
	y = s // 42
	while x < y:
		s += (y - x) * 2
		x = y
		y = s // 42
	print(s % (10 ** 9 + 7))
t = int(input())
for t_itr in range(t):
	s = int(input())
	y(s)


P = 10 ** 9 + 7

def steps(S):
	(q, r) = divmod(S, 20)
	return 42 * q + 2 * (r - int(r == 0))

def main():
	T = int(input())
	for _ in range(T):
		S = int(input())
		res = steps(S) % P
		print(res)
main()