Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight $u \oplus v$ (where $\oplus$ is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.


-----Input-----

The only line contains an integer n (2 ≤ n ≤ 10^12), the number of vertices in the graph.


-----Output-----

The only line contains an integer x, the weight of the graph's minimum spanning tree.


-----Example-----
Input
4

Output
4


-----Note-----

In the first sample: [Image] The weight of the minimum spanning tree is 1+2+1=4.

Difficulty: interview

Starter code:

Solutions:
a = [0]
cur = 1

while(cur < 10 ** 13):
    x = a[-1]
    a.append(x * 2 + cur)
    cur *= 2

n = int(input())
n -= 1

ans = 0
i = 1
cur = 1
while(n > 0):
    x = n % 2
    n = n // 2
    if(x > 0):
        ans += cur + a[i - 1]
    i += 1
    cur *= 2
    
print(ans)

n = int(input())
res = 0
inc = 1
while n > 1:
	res += inc*(n//2)
	n += 1
	n //= 2
	inc *= 2
print(res)


def f(n):
  if n == 2:
    return 1
  if n == 3:
    return 3
  if n % 2 == 0:
    return 2 * f(n // 2) + n // 2
  else:
    return 2 * f(n // 2 + 1) + n // 2

n = int(input())
print(f(n))

n = int(input())
a, t = n - 1, 1
n -= 1
i = 2
while i <= n:
    a += n // i * t
    i *= 2
    t *= 2
print(a)


"""
ATSTNG's ejudge Python3 solution template
(actual solution is below)
"""
import sys, queue

try:
    import dev_act_ffc429465ab634  # empty file in directory
    DEV = True
except:
    DEV = False

def log(*s):
    if DEV: print('LOG', *s)

class EJudge:
    def __init__(self, problem="default", reclim=1<<30):
        self.problem = problem
        sys.setrecursionlimit(reclim)

    def use_files(self, infile='', outfile=''):
        if infile!='':
            self.infile = open(infile)
            sys.stdin = self.infile
        if outfile!='':
            self.outfile = open(outfile, 'w')
            sys.stdout = self.outfile

    def use_bacs_files(self):
        self.use_files(self.problem+'.in', self.problem+'.out')

    def get_tl(self):
        while True: pass

    def get_ml(self):
        tmp = [[[5]*100000 for _ in range(1000)]]
        while True: tmp.append([[5]*100000 for _ in range(1000)])

    def get_re(self):
        s = (0,)[8]

    def get_wa(self, wstr='blablalblah'):
        for _ in range(3): print(wstr)
        return

class IntReader:
    def __init__(self):
        self.ost = queue.Queue()

    def get(self):
        return int(self.sget())

    def sget(self):
        if self.ost.empty():
            for el in input().split():
                self.ost.put(el)
        return self.ost.get()

    def release(self):
        res = []
        while not self.ost.empty():
            res.append(self.ost.get())
        return res

def tokenized(s):
    """ Parses given string into tokens with default rules """
    word = []

    for ch in s.strip():
        if ch == ' ':
            if word: yield ''.join(word); word = []
        elif 'a' <= ch <= 'z' or 'A' <= ch <= 'Z' or '0' <= ch <= '9':
            word.append(ch)
        else:
            if word: yield ''.join(word); word = []
            yield ch

    if word: yield ''.join(word); word = []

###############################################################################
ej = EJudge(  )
int_reader = IntReader()
fmap = lambda f,*l: list(map(f,*l))
parse_int = lambda: fmap(int, input().split())

# input
n = bin(int(input())-1)[2:][::-1]
log(n)
bit_full_cost = [(1 << i) * (i+1) for i in range(100)]
bit_cost = [1<<i for i in range(100)]
log(bit_cost)
ans = 0
for i in range(len(n)):
    if n[i] == '1':
        if i > 0: ans += bit_full_cost[i-1]
        ans += bit_cost[i]



print(ans)


'''
1 2 3 4 5 6 7 8


8 7
0 5
  0

'''



n = int(input())
level = 1
res = 0
while n >1:
    res  += level*(n//2)
    level *=2
    n = (n//2) + (n%2)

print(res)




import math

n = int(input())

ans = 0
cur = 1

while cur < n:
    cnt = math.ceil((n-cur)/(cur << 1))
    ans += cnt*cur
    cur <<= 1

print(ans)


n = int(input())
ans = 0
_pow = 2

while 2 * n > _pow:
    ans += (_pow //2 )* (n // _pow + (1 if n % _pow > _pow // 2 else 0))
    _pow *= 2
    
print(ans)


n = int(input())

ans2 = [0]

for i in range(1, 64):
  ans2.append(ans2[i - 1] + ans2[i - 1] + pow(2, i - 1))

def ans(n):
  if n == 0:
    return 0
  else:
    length = n.bit_length() - 1
    if n == pow(2, length):
      return ans2[length]
    else:
      return ans2[length] + ans(n - pow(2, length)) + pow(2, length)
print(ans(n))

n=int(input())-1
r=0
while n!=0:
    zz = 1
    a = 1
    z = 1
    while zz <= n:
        z<<=1
        zz<<=1
        zz+=1
        a<<=1
        a+=z
    zz>>=1
    a-=z
    a>>=1
    n-=zz
    r+=a
    if n:
        n-=1
        r+=z
print (r)

def func(n):
    if n==0:
        return 0
    if n==1:
        return 1
    if(n%2):
        return func(n//2)*2+(n//2)+1
    else:
        return func(n//2)*2+(n//2)
n=int(input())
a=[1,2,1,4,1,2,1,8,1,2,1,4,1,2,1]

print(func(n-1))


nn = input()
n = int(nn)
st = 0
dv = 1
step = []

while (dv <= n):
    step.append(dv)
    dv = dv*2
    st += 1
step.append(dv)
step.append(dv*2)
otv = 0
f = 1
q = 0
while (f != 0):
    if n == 0:
        break
    if n == 1:
        break
    for i in range (len(step)):
        if step[i] > n:
            q = i - 1
            break
    if (n == step[q]):
        otv += step[q-1] *(q)
        n -= step[q]
    else:
        otv += step[q] + step[q-1] *(q)
        n -= step[q]
print (otv)


def f(n):
    if n == 0:
        return 0
    return 2**(n-1) + 2*f(n-1)

f = [0]*60

for n in range(1, 60):
    f[n] = 2**(n-1) + 2*f[n-1]

n = int(input())

ans = 0

for k in range(60, 0, -1):
    if n >= 2**k:
        ans += f[k]
        n -= 2**k
        if n > 0:
            ans += 2**k

print(int(ans))

from sys import stdin, stdout


n = int(stdin.readline())
psze = 41
ans = 0


def trans(s):
    cnt = 0
    
    for i in range(psze * 2):
        if (i < len(s) and s[i] == '1'):
            cnt += (1 << i)
    
    return cnt

n -= 1

for i in range(psze):
    if 1 << i > n:
        break
    
    s = '0' * i + '1'
    cnt = 1
    
    l, r = 0, n + 1
    while (r - l > 1):
        m = (l + r) >> 1
        
        f = bin(m)[2:][::-1]
        
        if (trans(s + f) <= n):
            l = m
        else:
            r = m
    
    ans += (1 << i) * (l + 1)

stdout.write(str(ans))

a = int(input())

def ans(n, p=1):
    return ans( (n+1) // 2, p*2 ) + (n//2)*p if n > 1 else 0

print (ans(a))

from math import log

##n = int(input())
##
####print(n-1 + int(log(n-1)/log(2)))
##
##def ord2(n): ## max power of 2 that divides n
##    ret = 1
##
##    while n%ret == 0:
##        ret*=2
##
##    return ret//2
##
##total = 0
##
##for i in range(1, n):
##    total += ord2(i)

# fast way?

n = int(input()) - 1

divider = 2**int(log(n)/log(2))
total = 0
doubled = 0

while divider > 0:

    total += (n//divider - doubled)*divider

    ##print('A total of', n//divider, 'work, and the number of doubled', doubled)
    
    doubled += n//divider - doubled

    divider //=2

##    total = 0
##    power = 0
##
##    while 2**power <= n:
##
##        total += n//(2**power)
##
##        power += 1

print(total)


L = input().split()
n = int(L[0])
n -= 1
k = 0
while (1<<k)<n:
    k += 1
ans = 0
for i in range(0, k+1):
	ans += (1<<i)*((n+(1<<(i+1))-(1<<i))//(1<<(i+1)))
print(ans)

L=input().split();n=int(L[0])-1;k=0
while (1<<k)<n:
    k += 1
ans = 0
for i in range(0, k+1):
	ans+=(1<<i)*((n+(1<<(i+1))-(1<<i))//(1<<(i+1)))
print(ans)

n=int(input())-1;a=0
for i in range(0,40):
	k=1<<i;a+=k*((n+(k<<1)-k)//(k<<1))
print(a)

n=int(input())-1;a=0
for i in range(40):
	k=1<<i;a+=(n+k)//(k<<1)*k
print(a)

a=0;n=int(input())-1
for i in range(40):
	k=1<<i;a+=(n+k)//(k*2)*k
print(a)

f = lambda x: f(x // 2) * 2 + (x + 1) // 2 if x else 0
print(f(int(input()) - 1))

ans = 0
n = int(input())
k = 2**63
lpre = [0]
for i in range(50):
    lpre.append(lpre[-1]*2+2**i)
lmax = -1
for i in range(42,-1,-1):
    #print(i)
    if n&2**i:
        ans+=lpre[i]
        if lmax != -1:
            ans+=2**lmax
        lmax = i
print(ans)