There is a strange counter. At the first second, it displays the number $3$. Each second, the number displayed by decrements by $\mbox{1}$ until it reaches $\mbox{1}$. In next second, the timer resets to $2\times\textbf{the initial number for the prior cycle}$ and continues counting down. The diagram below shows the counter values for each time $\boldsymbol{\boldsymbol{t}}$ in the first three cycles:

Find and print the value displayed by the counter at time $\boldsymbol{\boldsymbol{t}}$.  

Function Description  

Complete the strangeCounter function in the editor below.  

strangeCounter has the following parameter(s):  

int t: an integer   

Returns  

int: the value displayed at time $\boldsymbol{\boldsymbol{t}}$  

Input Format

A single integer, the value of $\boldsymbol{\boldsymbol{t}}$.

Constraints

$1\leq t\leq10^{12}$

Subtask

$1\leq t\leq10^5$ for $60\%$ of the maximum score.

Sample Input
4

Sample Output
6

Explanation

Time $t=4$ marks the beginning of the second cycle.  It is double the number displayed at the beginning of the first cycle:$2\times3=6$. This is shown in the diagram in the problem statement.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
t = int(input())
t1 = 3
while t1 < t:
	t -= t1
	t1 *= 2
print(t1 - t + 1)


n = int(input())
dec = 3
while n > dec:
	n -= dec
	dec *= 2
print(dec - n + 1)


from sys import stdin, stdout
t = int(stdin.readline())
tempsCycle = 3
tAffiche = -1
while tAffiche == -1:
	if tempsCycle >= t:
		tAffiche = tempsCycle - t + 1
	else:
		t -= tempsCycle
	tempsCycle *= 2
print(tAffiche)


time = int(input())
t = 3
mult = 2
while time > t:
	t += 3 * mult
	mult *= 2
print(1 + (t - time))


def value_at_t(t):
	t_start = 1
	v_start = 3
	while True:
		if t_start <= t < t_start + v_start:
			return v_start - (t - t_start)
		else:
			t_start += v_start
			v_start *= 2
t = int(input())
print(value_at_t(t))


t = int(input())
value = 3
time = 1
while True:
	if t < time + value:
		print(value - (t - time))
		break
	(time, value) = (time + value, value * 2)


import sys
a1 = [1]
a2 = [3]
t = int(input())
br = int(1)
while a1[-1] <= t:
	a1.append(a1[br - 1] + a2[br - 1])
	a2.append(a2[br - 1] * 2)
	br += 1
res = a2[-2] - (t - a1[-2])
print(res)


t = int(input())
a = [0, 3]
s = 3
while s < t:
	a.append(a[-1] * 2)
	s += a[-1]
s -= a[-1]
print(a[-1] - (t - s) + 1)


t = int(input())

def strange(t):
	if t < 4:
		return 4 - t
	n = 0
	sumi = 0
	while True:
		if sumi + 3 * 2 ** n > t:
			break
		sumi += 3 * 2 ** n
		n += 1
	maxi = 3 * 2 ** n
	rem = t - sumi
	return maxi - rem + 1
print(strange(t))


import math
t = int(input())
d = math.ceil(math.log(((t - 3) / 2 + 3) / 3, 2))
top = (math.pow(2, d) - 1) * 6 + 3
print(int(top - t + 1))


import math

def solve(t):
	stage = int(math.log((t + 2) / 3, 2))
	a = []
	for i in range(stage + 2):
		a.append(sum(a) + 2 * i + 1)
	return a[-1] - t
t = int(input())
print(solve(t))


import math
n = int(input())
t = int(math.ceil(math.log(n / 3 + 1, 2)))
val = 3 * 2 ** (t - 1)
print(val - (n - val + 2))


max = 3
n_iter = int(input())
while n_iter > max:
	n_iter -= max
	max *= 2
counter = max + 1 - n_iter
print(counter)


(c, cmax) = (0, 3)
t = int(input().strip())
while c < t:
	c += cmax
	cmax *= 2
print(c - t + 1)


t = int(input())
k = 3
i = 1
while i <= t:
	i += k
	k *= 2
i = i - k // 2
print(k // 2 - (t - i))


from math import log, ceil
t = int(input())

def geom_sum(x):
	return int(3 * (2 ** x - 1))

def lower_sum(t):
	return int(ceil(log(t / 3 + 1) / log(2)))
print(geom_sum(lower_sum(t)) - t + 1)


t = int(input().strip())
start_time = 3
while t > start_time:
	t -= start_time
	start_time = start_time << 1
num = start_time - t + 1
print(num)


t = int(input())
(start, step) = (0, 3)
while t > start:
	start += step
	step *= 2
print(start - t + 1)


t = int(input().strip())
not_done = True
t_start = 3
c_start = 3
while not_done:
	if t < t_start:
		not_done = False
	else:
		c_start *= 2
		t_start += c_start
print(c_start - (t - (t_start - c_start)) + 1)


t = int(input())
n = 0
count = 0
while n < t:
	n += 3 * 2 ** count
	count += 1
print(n - t + 1)


import math
t = int(input().strip())
x = int(math.log((t + 2) / 3, 2))
st = 3 * (pow(2, x) - 1) + 1
p3 = 3 * pow(2, x)
ans = p3 - t + st
print(ans)


t = int(input())
x = 3
sum = 0
while sum < t:
	sum += x
	x *= 2
print(sum - t + 1)


import math as m
n = int(input())
x = m.ceil(m.log(m.ceil(n / 3) + 1, 2))
st = 3 * (2 ** (x - 1) - 1) + 1
end = 3 * (2 ** x - 1)
no = end - st + 1
diff = n - st + 1
print(no - diff + 1)


counter = 3
t = int(input().strip())
while t > counter:
	t -= counter
	counter *= 2
print(counter - t + 1)


import math
t = int(input().strip())
col = math.ceil(math.log2(t / 3 + 1))
colmax = (2 ** col - 1) * 3
print(colmax - t + 1)


t = int(input())
a = [3]
while sum(a) < t:
	a.append(a[-1] * 2)
print(a[-1] - (t - sum(a[:-1])) + 1)


import math
t = int(input())
k = 1
r = 3
while t > r:
	t -= r
	r *= 2
r -= t - 1
print(r)


t = int(input())
time = 1
value = 3
next_value = value * 2
next_time = value + time
while next_time < t:
	(time, value) = (next_value, next_time)
	next_value = next_value * 2
	next_time = value + time
if t == next_time:
	print(next_value)
else:
	diff = t - time
	result = value - diff
	print(result)


t = int(input())
c = 3
last = 3
while c < t:
	c += last * 2
	last = last * 2
print(c - t + 1)


t = int(input().strip())
multiply = 3
multCounter = 1
less = True
while less:
	if multiply < t:
		multCounter = multCounter * 2 + 1
		multiply = 3 * multCounter
	else:
		less = False
setTop = 1 + 3 * ((multCounter - 1) / 2)
setRange = setTop + 2
diff = abs(setTop - t)
output = setRange - diff
print(int(output))


t = int(input())
n = t // 3 + 1
i = 0
while n > 0:
	n //= 2
	i += 1
print(3 * (2 ** i - 1) + 1 - t)


t = int(input())
i = 0
tt = 3
while t - tt > 0:
	i += 1
	tt += 3 * 2 ** i
print(tt - t + 1)


import math
t = int(input())
n = int(math.log(t / 3 + 1, 2)) - 1
print(3 * 2 ** (n + 1) + 1 - (t - 3 * (2 ** (n + 1) - 1)))


import math

def isInt(x):
	if x - int(x) == 0:
		return True
	return False

def main():
	t = int(input())
	if t == 1:
		print(3)
	if t == 2:
		print(2)
	if t == 3:
		print(1)
	if t > 3:
		a = 3
		r = 2
		k = math.log(t / 3 + 1, 2)
		if isInt(k):
			print(1)
		else:
			n = int(k)
			s = 3 * (2 ** n - 1)
			term = a * r ** (n - 1)
			ans = 2 * term - (t - s) + 1
			print(int(ans))
main()


t = int(input())
ex = 0
x = 3
p = 3
i = 0
while ex <= t:
	ex = ex + 3 * pow(2, i)
	i += 1
i -= 1
ex = ex - 3 * pow(2, i)
x = 3 * pow(2, i)
p = x - (t - ex) + 1
print(p)


from sys import stdin
import math
t = int(input().strip())
p = 0
n = 0
while n < t:
	n += 3 * 2 ** p
	p += 1
p -= 1
first = n - 3 * 2 ** p + 1
ans = 3 * 2 ** p - (t - first)
print(ans)


import sys
t = int(input())
num_cycles = 0
t_temp = t
jump = 3
while t_temp > jump:
	t_temp -= jump
	jump *= 2
	num_cycles += 1
print(3 * pow(2, num_cycles) - t_temp + 1)


import math
number = int(input())

def answer(number):
	p = math.floor(math.log(number // 3 + 1, 2))
	maxSumOfSeriesThat = 3 * (2 ** p - 1)
	if maxSumOfSeriesThat == number:
		return 1
	else:
		return 3 * 2 ** p - (number - maxSumOfSeriesThat) + 1
print(answer(number))


t = int(input())
t1 = t // 3
power = 0
while 2 ** power - 1 <= t1:
	power += 1
t2 = t - 3 * (2 ** (power - 1) - 1)
if t2 == 0:
	n = 1
else:
	n = 3 * 2 ** (power - 1) - t2 + 1
print(n)


t = int(input())
T_now = 1
while 3 * (T_now - 1) < t:
	T_now *= 2
print(3 * T_now - (t + 2))


def solve(t):
	n = t
	if t < 3:
		return 4 - t
	L = []
	L.append(t % 3)
	t = t // 3
	while t:
		L.append(t % 2)
		t = t // 2
	y = L[-1] * 3 * pow(2, len(L) - 2)
	diff = n - y
	out = y - diff - 2
	if out <= 0:
		y = 2 * y
		diff = n - y
		out = y - diff - 2
	return out
print(solve(int(input())))


t = int(input().strip())
n = x = 0
while x < t:
	n = n + 1
	x = 3 * (2 ** n - 1)
print(x - t + 1)


from math import *

def genf(i):
	return ceil(3 * (pow(2, ceil(log(i / 3 + 1, 2))) - 1))
n = int(input())
print(genf(n) - n + 1)


import math
t = int(input())
r = int(math.log2((t - 1) // 3 + 1))
print(3 * 2 ** (r + 1) - t - 2)


import math
t = int(input())
cycle = int(math.ceil(math.log(t / 3 + 1, 2)))
starting_value = 3 * 2 ** (cycle - 1)
starting_t = (2 ** (cycle - 1) - 1) * 3 + 1
value = starting_value - (t - starting_t)
print(value)


import math
t = int(input())
p = math.log(t / 3 + 1, 2)
n = math.floor(p) + math.ceil(p - math.floor(p))
ans = 3 * 2 ** n - t - 2
print(ans)


t = int(input())
remainder = t % 3
poweroftwo = (t - t % 3) // 3
if remainder:
	poweroftwo += 1
index = len(bin(poweroftwo)[2:])
print(3 * (2 ** index - 1) - t + 1)


def solution(t):
	time = 1
	value = 3
	result = 0
	while True:
		next_t = time * 2 + 2
		if time <= t < next_t:
			result = value - (t - time)
			break
		time = next_t
		value *= 2
	return result
t = int(input().strip())
result = solution(t)
print(result)


t = int(input())
s = 3
v = 3
i = 1
c = 0
if t <= 3:
	print(3 - t + 1)
else:
	while True:
		v = v * 2
		s = v + s
		if t % s == t:
			c = i
			break
		elif t % s == 0 and t / s == 1.0:
			c = i
			break
		i = i + 1
	print(s - t + 1)


import math
t = int(input())
n = math.floor(math.log((t + 3) / 6, 2)) + 1
k1 = 3 * 2 ** n
k2 = 2 ** (n - 1) - 1
k3 = t - 3 - 6 * k2
k4 = k1 - k3 + 1
print(int(k4))


p = int(input())
count1 = 0
count2 = 0
if p <= 3:
	print(3 - (p - 1))
elif p > 3 and p <= 9:
	print(9 - (p - 1))
else:
	for i in range(int(p / 2)):
		z = 3 * pow(2, i)
		count1 = count1 + z
		if p > count2 and p <= count1:
			print(1 + (count1 - p))
			exit(0)
		count2 = count2 + z


t = int(input())
count = 3
temp = 3
total = 3
while True:
	if t <= total:
		print(total - t + 1)
		break
	else:
		total = total + temp * 2
		temp = temp * 2


import math
t = int(input())
s = 3
n = 1
while s < t:
	s += 6 * math.pow(2, n - 1)
	n += 1
print(int(s + 1 - t))


a = int(input())
x = 0
count = 3
score = 1
while x < a:
	x += count
	count *= 2
score += x - a
print(score)


t = int(input())
count = 3
temp = 3
total = 3
while True:
	if t <= total:
		print(total - t + 1)
		break
	else:
		total = total + temp * 2
		temp = temp * 2


import sys
import math
t = int(input().strip())
m = math.floor(math.log2((t - 1) // 3 + 1))
r = t - 3 * (2 ** m - 1)
print(3 * 2 ** (m + 1) - t - 2)


from math import log2
t = int(input().strip())
cycle = int(log2((t - 1) // 3 + 1))
cycle_start = 3 * 2 ** cycle
start_time = 3 * (2 ** cycle - 1) + 1
counter = cycle_start - (t - start_time)
print(counter)


import sys
t = int(input().strip())
n = 3
while t - n > 0:
	t = t - n
	n *= 2
print(n - t + 1)


from math import log
t = int(input())
gen = int(log((t + 2) / 3, 2))
gensize = 3 * 2 ** gen
li = t + 2 - gensize
print(gensize - li)


import sys
t = int(input().strip())
x = 1
while 3 * (x - 1) < t:
	x <<= 1
x = (x - 1) * 3
if x == t:
	print(1)
else:
	print(1 + (x - t))


import sys
t = int(input().strip())
cur = 1
counter = 3
while True:
	val = cur + counter
	if val <= t:
		cur = val
		counter = val + 2
	else:
		break
counter = counter - (t - cur)
print(counter)


import math
t = int(input())
n = math.floor(math.log((t + 3) / 6, 2)) + 1
k1 = 3 * 2 ** n
k2 = 2 ** (n - 1) - 1
k3 = t - 3 - 6 * k2
k4 = k1 - k3 + 1
print(int(k4))


from math import floor, log
t = int(input())
print(3 * 2 ** floor(log((t - 1) / 3 + 1, 2)) - t + 3 * (2 ** floor(log((t - 1) / 3 + 1, 2)) - 1) + 1)


import sys
import math
t = int(input().strip())
n = math.log10((t + 2) / 3) / math.log10(2)
n = math.floor(n)
nTop = math.floor(3 * math.pow(2, n))
tTop = nTop - 2
diff = t - tTop
print(nTop - diff)


import sys
t = int(input().strip())
tc = t
cycle = -1
twopow = (tc + 2) // 3
highbit = 0
while twopow > 0:
	twopow = twopow >> 1
	highbit += 1
highbit = 0 if highbit == 0 else highbit - 1
counter = 3 * 2 ** (highbit + 1) - tc - 2
print(counter)


import sys
from math import *
t = int(input().strip())
next_t = 3
while t - next_t > 0:
	t -= next_t
	next_t *= 2
print(next_t - (t - 1))


import sys
target = int(input().strip())
counter = 3
t = 1
while counter + t - 1 < target:
	t = t + counter
	counter *= 2
print(counter - (target - t))


from math import floor, log2
t = int(input())
res = 0
n = log2((t + 2) / 3)
if n.is_integer():
	res = int(3 * 2 ** n)
else:
	n = floor(n)
	res = 3 * 2 ** n + (t - (3 * 2 ** n - 2)) * -1
print(res)


import sys
t = int(input().strip())
n = 3
while True:
	if t <= n:
		break
	t -= n
	n *= 2
print(n - t + 1)


import sys
import math
t = int(input().strip())
y = int(math.log2((t + 2) // 3))
res = 3 * 2 ** (y + 1) - t - 2
print(res)


import sys
import math
t = int(input())
n = math.floor(math.log(t / 3 + 1) / math.log(2))
s = 3 * (2 ** n - 1)
remainder = t - s
answer = 3 * 2 ** n - remainder + 1
print(answer)


t = int(input().strip())
n = 2
while 3 * (n - 1) < t:
	n = 2 * n
print(3 * (n - 1) - t + 1)


t = int(input()) - 1
if t < 3:
	print([3, 2, 1][t])
else:
	startval = 3
	while t >= startval:
		t -= startval
		startval *= 2
	print(startval - t)


import sys

def stc(t):
	n = t
	i = 0
	while n > 0:
		n = int(n / 2) - 1
		i = i + 1
	p = 3 * 2 ** (i - 1)
	n = t - p + 2
	print(p - n)
t = int(input().strip())
stc(t)


tf = int(input())
t = []
t.append(1)
t.append(4)
t.append(10)
t.append(22)
t.append(46)
t.append(94)
t.append(190)
t.append(382)
t.append(766)
t.append(1534)
t.append(3070)
t.append(6142)
t.append(12286)
t.append(24574)
t.append(49150)
t.append(98302)
t.append(196606)
t.append(393214)
t.append(786430)
t.append(1572862)
t.append(3145726)
t.append(6291454)
t.append(12582910)
t.append(25165822)
t.append(50331646)
t.append(100663294)
t.append(201326590)
t.append(402653182)
t.append(805306366)
t.append(1610612734)
t.append(3221225470)
t.append(6442450942)
t.append(12884901886)
t.append(25769803774)
t.append(51539607550)
t.append(103079215102)
t.append(206158430206)
t.append(412316860414)
t.append(824633720830)
t.append(1000000000001)
nv = next((x[0] for x in enumerate(t) if x[1] > tf)) - 1
sum = 2 * t[nv] + 2 - tf
print(sum)


import sys
t = int(input().strip())
c = 3
t1 = 0
while t1 < t:
	t1 = t1 + c
	c = 2 * c
t1 = t1 - c
t1 = t - t1
c = c - t1 + 1
print(c)


t = int(input())
a = 3
while t > a:
	t -= a
	a <<= 1
print(a + 1 - t)


import sys
t = int(input().strip())
d = 3
while d < t:
	t = t - d
	d = d * 2
print(d - t + 1)


import sys
T = int(input().strip())
if T > 3:
	n = 0
	while 3 * (2 ** n - 1) < T:
		n += 1
	t = T % (3 * (2 ** (n - 1) - 1))
	print(1 + 3 * 2 ** (n - 1) - t)
else:
	print(4 - T)


import sys
t = int(input().strip())
(c, n, i) = (1, 3, 0)
while c < t:
	i += 1
	nxt = (2 ** i - 1) * 3 + 1
	if t >= nxt:
		(c, n) = (nxt, nxt + 2)
	else:
		break
print(n - (t - c))


t = int(input().strip())
(t1, rem) = divmod(t - 1, 3)
cycle = 0
t0 = 1
while t1:
	t0 += 3 * 2 ** cycle
	t1 = divmod(t1 - 1, 2)[0]
	cycle += 1
cycle0 = 3 * 2 ** cycle
print(t0 + cycle0 - t)


import sys
t = int(input().strip())
i = 3
t1 = 3
flag = 0
while t1 < t:
	i = i * 2
	t1 = t1 + i
	flag = 1
t1 -= i
t1 += 1
print(i - (t - t1))


import sys
t = int(input().strip())
n = 2
while 3 * (n - 1) < t:
	n = 2 * n
print(3 * (n - 1) - t + 1)


from math import log
n = int(input())
if n <= 3:
	c = 0
else:
	c = int(log(int((n - 1) / 3) + 1, 2))
start = 1 + 3 * (2 ** c - 1)
val = 3 * 2 ** c
print(val - (n - start))


import sys
t = int(input().strip())
n = 2
while 3 * (n - 1) < t:
	n = n * 2
print(3 * (n - 1) - t + 1)


import sys
t = int(input())
sum = 3
n = 1
while t > sum:
	n += 1
	sum = 3 * (pow(2, n) - 1)
d = t - 3 * (pow(2, n - 1) - 1)
print(3 * pow(2, n - 1) - d + 1)


ti = int(input())
(t, v) = (1, 3)
while 1:
	temp = t + v
	if ti < temp:
		break
	t = temp
	v = t + 2
print(v - (ti - t))


import sys
t = int(input().strip())
n = 2
while 3 * (n - 1) < t:
	n = 2 * n
print(3 * (n - 1) - t + 1)


import sys
import math
t = int(input().strip())
t -= 1
low = int(t / 3)
low_log = int(math.log(low + 1, 2))
res = 2 ** low_log * 3 - t
if low_log > 0:
	res += (2 ** low_log - 1) * 3
print(res)


t = int(input())
s = 3
while t > s:
	t -= s
	s *= 2
print(s - t + 1)


t = int(input())
if t == 1:
	print(3)
elif t == 2:
	print(2)
elif t == 3:
	print(1)
else:
	lis = []
	lis2 = [3]
	init = 3
	while True:
		if init > 10 ** 12:
			break
		else:
			lis.append(init)
		init *= 2
	for i in range(1, len(lis)):
		lis2.append(lis2[i - 1] + lis[i])
	up = -1
	pos = -1
	for i in range(len(lis2)):
		if t < lis2[i]:
			up = lis2[i]
			pos = i
			break
	val = up - lis2[pos - 1] - (up - t)
	print(lis[pos] - val + 1)


import math
t = int(input().strip())
h = int(math.log(1 + t // 3, 2))
print(pow(2, h + 1) * 3 - 1 - t - 1)


from math import *

def func():
	t = int(input())
	d = []
	for i in range(int(sqrt(t)) + 1):
		d.append([0, 0])
	a = 1
	b = 3
	d[0][0] = a
	d[0][1] = b
	i = 1
	while a < t:
		d[i][1] = 2 * d[i - 1][1]
		d[i][0] = d[i][1] - 2
		a = d[i][0]
		b = d[i][1]
		c = d[i - 1][0]
		e = d[i - 1][1]
		i = i + 1
	if a == t:
		print(b)
	else:
		print(e - (t - c))
func()


import sys

def cycles(i):
	if i == 0:
		return 3
	return 3 * 2 ** i + cycles(i - 1)
t = int(input().strip())
n = 0
while cycles(n) < t:
	n += 1
cycle_start_time = 3 * (2 ** n - 1) + 1
cycle = 3 * 2 ** n
if t == cycle_start_time:
	print(cycle)
else:
	print(cycle - (t - cycle_start_time))


import sys
t = int(input().strip())
start = 3
while t > start:
	t -= start
	start *= 2
print(start - t + 1)


import sys
t = int(input().strip())
c = 3
while c < t:
	t = t - c
	c = c * 2
print(c - t + 1)


time = int(input())
t = 3
c = 3
while True:
	if t > time:
		break
	else:
		c *= 2
		t = t + c
print(t - time + 1)