The Smart Beaver from ABBYY decided to have a day off. But doing nothing the whole day turned out to be too boring, and he decided to play a game with pebbles. Initially, the Beaver has n pebbles. He arranges them in a equal rows, each row has b pebbles (a > 1). Note that the Beaver must use all the pebbles he has, i. e. n = a·b.

<image> 10 pebbles are arranged in two rows, each row has 5 pebbles 

Once the Smart Beaver has arranged the pebbles, he takes back any of the resulting rows (that is, b pebbles) and discards all other pebbles. Then he arranges all his pebbles again (possibly choosing other values of a and b) and takes back one row, and so on. The game continues until at some point the Beaver ends up with exactly one pebble. 

The game process can be represented as a finite sequence of integers c1, ..., ck, where: 

  * c1 = n
  * ci + 1 is the number of pebbles that the Beaver ends up with after the i-th move, that is, the number of pebbles in a row after some arrangement of ci pebbles (1 ≤ i < k). Note that ci > ci + 1. 
  * ck = 1



The result of the game is the sum of numbers ci. You are given n. Find the maximum possible result of the game.

Input

The single line of the input contains a single integer n — the initial number of pebbles the Smart Beaver has.

The input limitations for getting 30 points are: 

  * 2 ≤ n ≤ 50



The input limitations for getting 100 points are: 

  * 2 ≤ n ≤ 109

Output

Print a single number — the maximum possible result of the game.

Examples

Input

10


Output

16


Input

8


Output

15

Note

Consider the first example (c1 = 10). The possible options for the game development are:

  * Arrange the pebbles in 10 rows, one pebble per row. Then c2 = 1, and the game ends after the first move with the result of 11. 
  * Arrange the pebbles in 5 rows, two pebbles per row. Then c2 = 2, and the game continues. During the second move we have two pebbles which can be arranged in a unique way (remember that you are not allowed to put all the pebbles in the same row!) — 2 rows, one pebble per row. c3 = 1, and the game ends with the result of 13. 
  * Finally, arrange the pebbles in two rows, five pebbles per row. The same logic leads us to c2 = 5, c3 = 1, and the game ends with the result of 16 — the maximum possible result.

Difficulty: EASY
Tags: Number theory

Starter code:

Solutions:
n = int(input())
r = n + 1
i = 2
s = n ** 0.5
while i <= s:
	if n % i == 0:
		r += n // i
		n //= i
		s = n ** 0.5
		i = 1
	i += 1
print(r)


from math import sqrt, ceil
n = int(input())
c = n
while n > 1:
	b = 1
	for v in range(2, ceil(sqrt(n)) + 1):
		if n % v == 0:
			m = max(v, n // v)
			if n != m:
				b = max(m, b)
	n = b
	c += n
print(c)


n = int(input())
from math import sqrt
ans = n
while n != 1:
	divisor = 1
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			divisor = i
			break
	if divisor == 1:
		ans += 1
		break
	ans += n // divisor
	n = n // divisor
print(ans)


arr = []
p = 2
while True:
	x = p * p
	if x <= 10 ** 9:
		arr.append(p)
	else:
		break
	p += 1
n = int(input())
ans = n
while True:
	f = -1
	for i in arr:
		if n % i == 0:
			f = i
			break
	if f == -1:
		break
	else:
		ans += n // f
		n = n // f
print(ans)


def maxsum(n):
	ans = 0
	while n > 1:
		ans += n
		for i in range(2, n + 1):
			if n % i == 0:
				n = n // i
				break
	return ans + 1
n = int(input())
print(maxsum(n))


n = int(input())
a = 0
b = 2
ans = n
while b > 1:
	for z in range(2, n + 1):
		if z == n:
			b = 1
			ans += b
			break
		elif n % z == 0:
			b = int(n / z)
			ans += b
			n = b
			break
print(ans)


n = int(input())
i = 2
Sum = n
while True:
	if i ** 2 > n:
		Sum += 1
		break
	elif n % i == 0:
		n = n // i
		Sum += n
	else:
		i += 1
print(Sum)


from collections import deque, defaultdict, Counter
from itertools import product, groupby, permutations, combinations
from math import gcd, floor, inf, log2, sqrt, log10
from bisect import bisect_right, bisect_left
from statistics import mode
from string import ascii_uppercase

def divisors(x):
	divs = [1]
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			divs.append(i)
			divs.append(x // i)
			break
	return max(divs)
n = int(input())
ans = n
prev = inf
while True:
	x = divisors(n)
	if x < prev:
		ans += x
		prev = x
	n -= x
	if x == 1:
		break
print(ans)


import math
n = int(input())
p = n
factor = []
while n % 2 == 0:
	factor.append(2)
	n //= 2
for i in range(3, int(math.sqrt(p)) + 1, 2):
	while n % i == 0:
		factor.append(i)
		n //= i
if n != 1:
	factor.append(n)
total = p
for i in range(len(factor)):
	p = p // factor[i]
	total += p
print(total)


n = int(input())
count = 0

def pebbles(n, count):
	count += n
	if n == 1:
		return count
	else:
		for i in range(n // 2):
			if int(n / (n // 2 - i)) == n / (n // 2 - i):
				a = n // 2 - i
				b = n / (n // 2 - i)
				return pebbles(a, count)
print(pebbles(n, count))


n = int(input())
result = n
while n != 1:
	a = 2
	while a * a <= n:
		if n % a == 0:
			break
		a += 1
	if a * a > n:
		n = 1
	else:
		n //= a
	result += n
print(result)


import math
c = int(input())
sum = c
while c > 1:
	signal = False
	for i in range(2, int(math.sqrt(c)) + 1):
		if c % i == 0:
			c = c // i
			signal = True
			break
	if signal == False:
		c = 1
	sum += c
print(sum)


n = int(input())
i = 2
sum = n
P = [0 for i in range(n + 1)]
while True:
	if n == 1:
		break
	elif P[i] == 1:
		i += 1
	elif n % i == 0:
		n = n // i
		sum += n
		i = 2
	else:
		j = i
		while j < n:
			P[j] = 1
			j += i
		i += 1
print(sum)


N = int(input())
ans = N
lastD = 2
while N > 1:
	nextD = None
	for i in range(lastD, int(N ** (1 / 2)) + 1):
		if N % i == 0:
			nextD = i
			break
	if nextD != None:
		ans += N // nextD
		N //= nextD
	else:
		ans += 1
		N = 1
print(ans)


def main():
	n = int(input())
	sum_points = n
	from math import floor, sqrt
	while n > 1:
		try:
			max_divisor = floor(sqrt(n)) + 1
			divisor = next((i for i in range(2, max_divisor) if n % i == 0))
			while n % divisor == 0:
				n //= divisor
				sum_points += n
		except StopIteration:
			n = 1
			sum_points += n
	print(sum_points)
main()


def ld(n):
	k = int(n ** 0.5)
	for i in range(2, k + 2):
		if i == k + 1:
			return 1
		elif n % i == 0:
			return n // i
n = int(input())
ans = 1
while n != 1:
	ans += n
	n = ld(n)
print(ans)


num = int(input())

def magic(var):
	iterations = num
	counter = 2
	while var > 1:
		if var % counter == 0:
			var = var // counter
			iterations += var
		else:
			counter += 1
	return iterations
print(magic(num))


from math import sqrt

def f(n):
	global count
	for i in range(2, int(sqrt(n)) + 2):
		if n % i == 0 and n / i != 1:
			count += n / i
			return f(n / i)
	return count + 1
n = int(input())
count = n
print(int(f(n)))


n = int(input())
count = n
while n > 1:
	a = int(n ** 0.5) + 1
	for i in range(2, a):
		if n % i == 0:
			count += n // i
			n //= i
			break
	else:
		count += 1
		break
print(count)


n = int(input())
(i, s) = (2, n)
while n > 1:
	if n % i:
		i += 1
	else:
		n //= i
		s += n
print(s)


n = int(input())

def pebbles(n, count):
	maxi = 0
	a = 2
	while a * a <= n:
		b = n / a
		if b % 1 == 0 and b > maxi:
			maxi = b
		a += 1
	count += maxi
	if maxi == 0:
		count += 1
		print(count)
		return
	pebbles(int(maxi), int(count))
if n == 1:
	print(1)
else:
	pebbles(n, n)


import math
n = int(input())
c = n
while c > 1:
	z = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			c += n // i
			n = n // i
			z = 1
			break
	if z == 0:
		c += 1
		break
print(c)


n = int(input())

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
c = n + 1
while n > 1:
	if n % 2 == 0:
		n //= 2
		if n != 1:
			c += n
	elif isPrime(n):
		n = 1
	else:
		j = 3
		while n % j > 0:
			j += 1
		n //= j
		c += n
print(c)


from collections import Counter

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

def main():
	n = int(input())
	res = n
	for e in factors(n):
		n //= e
		res += n
	print(res)
main()


def greatestFactor(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return int(x / i)
		else:
			i = i + 1
	if i * i > x:
		return 1
x = int(input())
c = x
while x != 1:
	c = c + greatestFactor(x)
	x = greatestFactor(x)
print(c)


n = int(input())
i = 2
s = n
m = int(n ** 0.5)
while n > 1 and i <= m:
	if n % i:
		i += 1
	else:
		n //= i
		s += n
print(s + (n > 1))


n = int(input())
ans = n
while n > 1:
	for i in range(2, n + 1):
		if n % i == 0:
			ans += n // i
			n //= i
			break
print(ans)


n = int(input())
L = [n]

def prime_list(x):
	Lprem = [2, 3, 5]
	if x >= 6:
		candidates = [1, 3, 7, 9]
		for k in range(6, x + 1):
			last_digit = int(str(k)[-1])
			if last_digit not in candidates:
				continue
			else:
				Lk = [(k / i).is_integer() for i in Lprem]
				if True not in Lk:
					Lprem.append(k)
	else:
		for i in range(2):
			if x >= Lprem[i] and x < Lprem[i + 1]:
				Lprem = Lprem[:i + 1]
				break
	return Lprem
primes = prime_list(n)
while n != 1:
	if n in primes:
		n = 1
		L.append(n)
	else:
		for prime in primes:
			if n % prime == 0:
				n = n // prime
				L.append(n)
				break
print(sum(L))


def isprime(n):
	if n == 2:
		return True
	else:
		i = 2
		while i * i <= n:
			if n % i == 0:
				return False
			i = i + 1
		return True
n = int(input())
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
	l = int(i ** (1 / 2))
	if isprime(i) == True:
		table[i] = i + 1
	else:
		for j in range(2, l + 1):
			if i % j == 0:
				table[i] = max(table[i], i + max(table[j], table[i // j]))
print(table[n])


from sys import *
import math

def next_c(c):
	x = int(math.sqrt(c))
	i = 2
	while i <= x:
		if c % i == 0:
			return int(c / i)
			break
		else:
			i = i + 1
	if i > x:
		return 1

def game(n):
	sum = n
	r = next_c(n)
	while r != 1:
		sum = sum + r
		r = next_c(r)
	return sum + 1
n = int(input())
print(game(n))


import math
n = int(input())
result = 0
num = 2
sqrt_n = math.sqrt(n)
result += n
while num <= sqrt_n:
	if n % num == 0:
		result += n // num
		n //= num
		sqrt_n = math.sqrt(n)
		num = 1
	num += 1
result += 1
print(result)


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
ORDA = 97

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	new_number = 0
	while number > 0:
		new_number += number % base
		number //= base
	return new_number

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True
n = ii()
cnt = n
i = 2
while i < int(n ** 0.5) + 1:
	if n % i == 0:
		n //= i
		cnt += n
		i = 2
	else:
		i += 1
	if prime(n):
		break
print(cnt + 1)


cnt = lambda s, i: s.count(i)
ii = lambda : int(input())
si = lambda : input()
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
n = ii()
s = n
m = int(n ** 0.5) + 1
i = 2
while n >= 1 and i < m:
	if n % i:
		i += 1
	else:
		n //= i
		s += n
print(s + (n > 1))


import math

def maxsum(n):
	ans = 0
	while n > 1:
		ans += n
		flag = 0
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				flag = 1
				n = n // i
				break
		if flag == 0:
			break
	return ans + 1
n = int(input())
print(maxsum(n))


n = int(input())
d = 2
r = 1
while d * d <= n:
	while n % d < 1:
		r += n
		n //= d
	d += 1
if n > 1:
	r += n
print(r)


from collections import defaultdict
import math

def solve(n):
	sq = math.ceil(n ** 0.5)
	ans = 0
	for i in range(2, sq + 1):
		while n % i == 0:
			ans += n
			n //= i
	return ans + n + (n > 1)
print(solve(int(input())))


n = int(input())
ans = n
while n > 1:
	f = 0
	for ff in range(2, n):
		if n % ff == 0:
			f = max(f, max(ff, n // ff))
	if f == 0:
		ans += 1
		break
	ans += f
	n = f
print(ans)


def f(n):
	if n in memo.keys():
		return memo[n]
	l = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			l.append(i)
			g = n // i
			if not f in l:
				l.append(g)
		i += 1
	if len(l) == 0:
		memo[n] = n + 1
		return memo[n]
	list2 = list(map(f, l))
	memo[n] = n + max(list2)
	return memo[n]
n = int(input())
memo = {1: 1}
print(f(n))


import math

def f(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return n // i
	return 1
n = int(input())
(ans, b) = (n, n)
while b != 1:
	b = f(b)
	ans += b
print(ans)


n = int(input())

def game(n):
	result = n
	x = n
	while n > 1:
		for i in range(2, x + 1):
			if n % i == 0:
				result = result + n // i
				break
		n = n // i
	return result
print(game(n))


n = int(input())
res = n
while n != 1:
	i = 2
	while n % i != 0:
		i += 1
	n //= i
	res += n
print(res)


def factors(N):
	ans = []
	cur = 2
	B = int(N ** (1 / 2)) + 1
	while N != 1 and cur < B:
		while N % cur == 0:
			N //= cur
			ans += [cur]
		cur += 1
	if N != 1:
		ans += [N]
	ans.sort()
	return ans
N = int(input())
fs = factors(N)
ans = N
cur = N
ind = 0
while ind < len(fs):
	N //= fs[ind]
	ans += N
	ind += 1
print(ans)


def recgame(n):
	a = n
	sum = a
	while a != 1:
		for i in range(int(2), int(a + 1)):
			if a % i == 0:
				a = a / i
				sum += a
				break
	return int(sum)
n = int(input())
print(recgame(n))


num = int(input())
div = 2
total = 1
while num > 1:
	if div * div > num:
		total += num
		break
	elif num % div == 0:
		total += num
		num /= div
	else:
		div += 1
print(int(total))


def find(n):
	if n % 2 == 0:
		return 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return i
	return n
n = int(input())
r = n
while n != 1:
	n = n / find(n)
	r += n
print(int(r))


def isPrime(n):
	if n <= 1:
		return False
	for i in range(2, n):
		if n % i == 0:
			return False
	return True

def number(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return n // i
		else:
			continue
n = int(input())
count = n
left = n
while left > 1:
	if isPrime(left):
		break
	else:
		count += number(left)
		left = number(left)
count += 1
print(count)


def sieve(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return x // i
		i += 1
	else:
		return 1
n = int(input())
c = n
ans = c
while c != 1:
	c = sieve(c)
	ans += c
print(ans)


n = int(input())
sum = n
col = []
while n > 1:
	for i in range(2, n + 1):
		for j in range(1, n):
			if i * j == n:
				col.append(j)
	sum = sum + max(col)
	n = max(col)
	col = []
print(sum)


from math import *
n = int(input())

def func(n):
	if n % 2 == 0:
		return n // 2
	else:
		i = 3
		while i <= int(sqrt(n)):
			if n % i == 0:
				return n // i
				break
			else:
				i += 2
	return 1
s = 0
while n > 1:
	s += n
	n = func(n)
print(s + 1)


import math

def divisors(n):
	i = 2
	l = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				l.append(i)
			else:
				l.extend([i, n // i])
		i = i + 1
	return l

def pebbles(n):
	if divisors(n) == []:
		return n + 1
	else:
		c = divisors(n)
		m = min(c)
		return n + pebbles(n // m)
n = int(input())
print(pebbles(n))


def largest_divisor(X):
	A = []
	for i in range(1, X):
		if X % i == 0:
			A.append(i)
	return max(A)
n = int(input())
ans = n
while largest_divisor(n) > 1:
	ans = ans + largest_divisor(n)
	n = largest_divisor(n)
print(ans + 1)


__author__ = 'Esfandiar'
import sys
input = sys.stdin.readline
n = int(input())
res = n
while n:
	f = 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			res += n // i
			n //= i
			f = 0
			break
	if f:
		res += 1
		break
print(res)


n = int(input())
sum = n
b = 0
while b != 1:
	for i in range(2, n + 1):
		if n % i == 0:
			b = n // i
			break
	sum = sum + b
	n = b
print(sum)


n = int(input())
k = n
t = n
while t != 1:
	l = []
	for i in range(1, t):
		if t % i == 0:
			l.append(i)
	k += max(l)
	t = max(l)
print(k)


n = int(input())
a = {}

def search(k):
	if k not in a:
		t = 1
		i = 2
		while i * i <= k:
			if k % i == 0:
				t = max(t, search(i), search(k // i))
			i += 1
		a[k] = k + t
	return a[k]
print(search(n))


cntReal = int(input())
counter = 2
result = cntReal
puf = cntReal
if cntReal == 456345677:
	print(cntReal + 1)
elif cntReal == 999999937:
	print(cntReal + 1)
else:
	while True:
		if cntReal % counter == 0:
			cntReal //= counter
			result += cntReal
			counter = 2
		else:
			counter += 1
		if cntReal == 1 or counter >= puf ** 2:
			break
	print(result)


def pr(x):
	for i in range(3, round(x ** 0.5) + 2, 2):
		if x % i == 0:
			return i
		else:
			continue
	return x
n = int(input())
(ans, x) = (n, n)
l = [3, 5, 7, 11, 13]
while x > 1:
	if x % 2 == 0:
		ans += x // 2
		x = x // 2
	elif x in l:
		ans += 1
		x = 1
	elif x == 9:
		ans += 3
		x = 3
	else:
		divisor = pr(x)
		ans += x // divisor
		x = x // divisor
print(ans)


n = int(input())
k = 2
ans = n
while k * k <= n:
	while n % k == 0:
		n //= k
		ans += n
	if k == 2:
		k = 3
	else:
		k += 2
if n > 1:
	ans += 1
print(ans)


n = int(input())
r = n
k = n - 1
while n != 1:
	if n % k == 0:
		n = k
		r += k
	k -= 1
print(int(r))


n = int(input())
m = n
while n > 1:
	div = 2
	while n % div != 0:
		div += 1
	m += n // div
	n = n // div
print(m)


n = int(input())
sum = n
i = 2
while n > 1:
	if n % i != 0:
		i += 1
	else:
		n = n // i
		sum += n
print(sum)


import math
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 11897, 36709, 1187, 1193, 1201, 1213, 1217, 31607]
n = int(input())
tot = n
for i in range(len(primes)):
	while n % primes[i] == 0:
		tot += n // primes[i]
		n = n // primes[i]
if n == 1:
	print(tot)
else:
	print(tot + 1)


def calc(n):
	j = int(n // 2)
	c = 1
	while j > 1:
		if n % j == 0:
			c = j
			break
		j = j - 1
	return c
n = int(input())
sm = 0
while n > 1:
	sm = sm + n
	n = calc(n)
print(sm + 1)


s = n = int(input())
while n > 1:
	for d in range(2, int(n ** 0.5) + 1):
		if n % d == 0:
			n //= d
			s += n
			break
	else:
		break
print(s + (n > 1))


import sys
import math
n = int(input())
(a, b, t) = (0, 0, n)
f2 = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824]
if n in f2:
	print(int(2 * 2 ** math.log(n, 2) - 1))
	sys.exit()
while n > 1:
	if n in f2:
		print(int(t + 2 * 2 ** math.log(n, 2) - 1))
		sys.exit()
	if n % 2 == 0:
		t += n / 2
		n -= n / 2
	else:
		a = 3
		b = n / a
		while b % 1 != 0:
			a += 2
			b = n / a
		n = b
		t += b
print(int(t))


n = int(input())
ans = n
while n != 1:
	i = 2
	while n % i != 0:
		i += 1
	n //= i
	ans += n
print(ans)


def scorefunc(score, num):
	if num == 1:
		return score
	else:
		for j in range(2, num + 1):
			if num % j == 0:
				row = j
				num = num // j
				score += num
				return scorefunc(score, num)
n = int(input())
score = n
num = n
print(scorefunc(score, num))


a = int(input())
c = a
while a > 1:
	for i in range(1000000000):
		if a % (i + 2) == 0:
			c += a / (i + 2)
			a = a / (i + 2)
			break
c = int(c)
print(c)


import sys
n = int(sys.stdin.readline())
ans = 0
while n > 1:
	startMn = 2
	founded = False
	while startMn <= n ** 0.5:
		if n % startMn == 0:
			ans += n
			n = n // startMn
			founded = True
			break
		startMn += 1
	if not founded:
		ans = ans + n
		n = 1
ans = ans + n
print(ans)


import math as m
n = int(int(input()))
a = n + 1
while n % 2 == 0 and n > 2:
	a += n // 2
	n //= 2
for i in range(3, int(m.sqrt(n)) + 1):
	if n % i == 0 and n > i:
		a += n // i
		n //= i
print(a)


from sys import stdin
import math

def GCD(a, b):
	if a > b:
		big = a
		small = b
	else:
		big = b
		small = a
	while big % small != 0:
		tmp = big % small
		big = small
		small = tmp
	return small

def getSmallestDivisor(n):
	num = 1
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return i
	return 1
n = int(input())
score = n
while n != 1:
	div = getSmallestDivisor(n)
	if div == 1:
		n = 1
	else:
		n = n / div
	score = score + n
print(int(score))


import math

def prime(n, lis):
	while n % 2 == 0:
		lis.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lis.append(i)
			n = n / i
	if n > 2:
		lis.append(n)
m = int(input())
ans = m
while 1 > 0:
	lis = []
	prime(int(m), lis)
	if len(lis) == 1:
		ans += 1
		break
	lis.sort()
	ans += m // lis[0]
	m = m // lis[0]
print(int(ans))


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from itertools import combinations, permutations
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
n = ii()
k = 2
ans = 0
while k * k <= n:
	while n % k == 0:
		ans += n
		n //= k
	k += 1
if n > 1:
	ans += n
print(ans + 1)


a = int(input())
c = a
while a > 1:
	v = 0
	for i in range(2, int(a ** 0.5) + 1):
		if a % i == 0:
			a //= i
			c += a
			v = 1
			break
	if not v:
		c += 1
		break
print(c)


def prime(n):
	if n == 2 or n == 3:
		return True
	elif n % 2 == 0:
		return False
	else:
		for i in range(3, int(n ** 0.5) + 1, 2):
			if n % i == 0:
				return False
		return True

def factors(n):
	l = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			l.append(i)
			if i != n ** 0.5:
				l.append(n // i)
	return l

def solution(n):
	if prime(n):
		return n + 1
	else:
		ans = n
		l = factors(n)
		x = min(l)
		y = n // x
		ans = ans + y
		n = y
		while not prime(n):
			l = factors(n)
			x = min(l)
			y = n // x
			ans = ans + y
			n = y
		ans = ans + 1
		return ans
n = int(input())
print(solution(n))


def isPrime(num):
	if num > 1:
		for i in range(2, num):
			if num % i == 0:
				return False
				break
		else:
			return True
	else:
		return False

def RectangularGame(n):
	sum = n
	if n == 1:
		return 1
	elif isPrime(n):
		return n + 1
	else:
		for i in range(2, n):
			if n % i == 0:
				sum = sum + RectangularGame(n // i)
				return sum
			else:
				continue
number = int(input())
print(RectangularGame(number))


n = int(input())
import math

def prime(n):
	l = [0 for i in range(n + 1)]
	for j in range(2, int(math.sqrt(n)) + 1):
		if l[j] == 0:
			k = 2 * j
			while k < n + 1:
				l[k] = 1
				k += j
	return l

def div(n):
	l = [0 for _ in range(n + 1)]
	i = 2
	while i < n:
		if l[i] == 0:
			if n % i == 0:
				return i
			j = i
			while j < n + 1:
				l[j] = 1
				j += i
		i += 1

def pebbles(n):
	s = n
	l = prime(n)
	while n > 1:
		if l[n] == 0:
			break
		n = int(n / div(n))
		s += n
	return s + 1
print(pebbles(n))


def prime_test(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return False
	return True

def function(n):
	count = 0
	ans = n
	m = 2
	while m <= n:
		if n % m == 0:
			ans += n // m
			n = n // m
		else:
			m += 1
			count += 1
			if count >= 10 ** 6:
				if prime_test(n):
					ans += 1
					break
	return ans
n = int(input())
print(function(n))


from sys import *

def calc(n):
	z = n
	c = 0
	x = n // 2
	while x > 0:
		if n % x == 0:
			c = c + x
			n = x
			x = x // 2
		else:
			x -= 1
	print(c + z)
n = int(input())
calc(n)


def ksmall(n):
	for i in range(2, n + 1):
		p = i
		if n % p == 0:
			break
	return p

def ur(n):
	p = ksmall(n)
	if n == p:
		return n + 1
	else:
		return n + ur(n // p)
e = int(input())
print(ur(e))


def min_div(num):
	for i in range(2, int(num ** 0.5) + 1):
		if num % i == 0:
			return i
	return 1
n = int(input())
count = n
while min_div(n) != 1:
	n = n // min_div(n)
	count += n
count += 1
print(count)


import math
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271]
n = int(input())
tot = n
for i in range(len(primes)):
	while n % primes[i] == 0:
		tot += n // primes[i]
		n = n // primes[i]
print(tot)


n = int(input())
t = 2
c = 0
while n != 1:
	if n % t == 0:
		c = c + n
		n = n / t
		t = 2
	else:
		t = t + 1
c = c + 1
print(int(c))


import math
n = int(input())
sum = n
x = n
while x != 1:
	f = True
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			x = x // i
			f = False
			break
	if f:
		x = 1
	sum += x
print(sum)


from sys import stdin
from math import sqrt
input = stdin.readline
n = int(input())
ans = n
s = int(sqrt(n))
fact = []
for i in range(1, s + 1):
	if n % i == 0:
		fact.append(i)
		fact.append(n // i)
if fact[-1] == fact[-2]:
	fact.pop()
fact.sort()
i = len(fact) - 2
j = len(fact) - 1
while i >= 0:
	if fact[j] % fact[i] == 0:
		ans += fact[i]
		j = i
	i -= 1
print(ans)


n = int(input())
y = int(n)
h = int(0)
c = int(0)
while y != 0:
	c = c + y
	for i in range(1, y + 1):
		if y % i == 0 and i != 1:
			h = i
			break
	if h == 0:
		h = 1
	y = y // h
print(c)


import math
n = int(input())
ans = n
i = 1
while True:
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			ans = ans + n // i
			n = n // i
			break
	else:
		ans = ans + 1
		break
print(ans)


def largestDivisor(n):
	if n == 1:
		return 1
	i = n - 1
	while i >= 1:
		if n % i == 0:
			return i
		i -= 1

def gameResult(n):
	points = n
	while n > 1:
		points = points + largestDivisor(n)
		n = largestDivisor(n)
	return points
x = int(input())
print(gameResult(x))


import sys, math, string, bisect
input = sys.stdin.readline
from collections import deque
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
n = I()
c = n
while n != 1:
	p = 2
	k = n
	while p < n ** 0.5 + 1:
		if n % p == 0:
			c += n // p
			n = n // p
			break
		p += 1
	if n == k:
		c += 1
		n = 1
print(c)


a = int(input())
b = 2
contador = a
while a > 1:
	if a % b == 0:
		a = a // b
		contador += a
	else:
		b += 1
print(contador)


n = int(input())
sum = n
while True:
	if n == 1:
		break
	q = int(n ** 0.5)
	for i in range(2, q + 1):
		if n % i == 0 and i != 1:
			n = n // i
			sum += n
			break
	else:
		sum += 1
		n = 1
		break
print(sum)


n = int(input())

def stone(n):
	for i in range(n, 1, -1):
		if n % i == 0:
			q = n // i
	return q

def result(n):
	s = n
	while n > 1:
		s = s + stone(n)
		n = stone(n)
	return s
print(result(n))


def pebble(n):
	if n == 1:
		return 1
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return n + pebble(n // i)
		return n + 1
n = int(input())
print(pebble(n))


def function(n):
	ans = n
	m = 2
	while m <= n:
		if n % m == 0:
			ans += n // m
			n = n // m
		else:
			m += 1
	return ans
n = int(input())
print(function(n))


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 pebbles(n, k):
	k += n
	if n == 1:
		return int(k)
	else:
		n = n / smallestDivisor(n)
		return pebbles(n, k)
n = int(input())
print(pebbles(n, 0))


n = int(input())
c = n
while n > 1:
	if n % 2 == 0:
		c += n // 2
		n = n // 2
	else:
		x = n // 2
		while True:
			if n % x == 0:
				c += x
				n = x
				break
			else:
				x -= 1
print(c)


from math import sqrt
n = int(input())
Sum = n
while n % 2 == 0:
	n = n // 2
	Sum += n
i = 3
while i <= int(sqrt(n)):
	while n % i == 0:
		n = n // i
		Sum += n
	i += 2
if n > 2:
	Sum += 1
print(Sum)


N = int(input())
sum = N
for j in range(2, N + 1):
	while N % j == 0:
		N //= j
		sum += N
print(sum)


n = int(input())
sum = n
while n % 2 == 0:
	n = n // 2
	sum = sum + n
i = 3
while i <= int(n ** 0.5):
	while n % i == 0:
		n = n // i
		sum = sum + n
	i = i + 2
if n > 2:
	sum = sum + 1
print(sum)


def f1(x):
	for i in range(2, x):
		if x % i == 0:
			return i
	return 1
n = int(input())
m = n
while 1:
	if f1(n) == 1:
		break
	n = int(n / f1(n))
	m = m + n
print(m + 1)


n = int(input())
t = n

def search_simple(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return n
A = []
s = 1
while s != n:
	a = int(search_simple(t))
	t /= a
	s *= a
	A.append(a)
V = n
d = n
for i in range(len(A)):
	V += int(d / A[i])
	d /= A[i]
print(V)


n = int(input())
ans = n
k = n // 2
if n == 1:
	ans = 1
else:
	while True:
		if k == 1:
			ans += 1
			break
		while k > 1:
			if n % k == 0:
				ans += k
				n = k
				k -= 1
			else:
				k -= 1
print(ans)


def big_f(n):
	f = 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			f = n // i
			break
	return f
z = int(input())
total = z
while z > 1:
	z = big_f(z)
	total += z
print(total)


(X, SUM) = (int(input()), 0)
while X != 1:
	(Found, SUM) = (False, SUM + X)
	for i in range(2, X + 1):
		if X % i == 0:
			X = X // i
			break
print(SUM + 1)


def primeFact(n):
	ans = []
	i = 3
	num = n
	while n % 2 == 0:
		ans.append(2)
		n = n / 2
	num = n
	while i * i < num + 1:
		while n % i == 0:
			ans.append(i)
			n = n / i
		i += 2
	if n > 1:
		ans.append(int(n))
	return ans
n = int(input())
facts = primeFact(n)
ans = n
for i in facts:
	n = n // i
	ans += n
print(ans)


n = int(input())
res = n
while n != 1:
	i = 2
	while i * i <= n:
		if not n % i:
			break
		i += 1
	if i * i > n:
		n = 1
	else:
		n //= i
	res += n
print(res)


__author__ = 'Esfandiar'
n = int(input())
res = n
while n:
	f = 1
	for i in range(2, n // 2 + 1):
		if n % i == 0:
			res += n // i
			n //= i
			f = 0
			break
	if f:
		res += 1
		break
print(res)


import sys
import math
get_string = lambda : sys.stdin.readline().strip()
get_int_list = lambda : list(map(int, sys.stdin.readline().strip().split()))
get_int = lambda : int(sys.stdin.readline())

def factors(n):
	i = 2
	s = set()
	while i * i <= n:
		if n % i == 0:
			s.add(i)
			s.add(n // i)
		i += 1
	s.add(1)
	return s
n = get_int()
count = n
while n != 1:
	m = max(factors(n))
	count += m
	n = m
print(count)


n = int(input())
sum_ = 0
while n != 1:
	sum_ += n
	max_ = 0
	for i in range(2, n + 1):
		if n % i == 0:
			max_ = max(max_, n // i)
	n = max_
	assert n != 0
print(sum_ + 1)


def smallest_factor(n):
	i = 2
	while i * i <= n and n % i != 0:
		i = i + 1
	if n % i == 0:
		return i
	else:
		return n

def max_number_in_row(n):
	return n // smallest_factor(n)

def max_sum(n):
	if n == 1:
		return 1
	else:
		return n + max_sum(max_number_in_row(n))
n = int(input())
print(max_sum(n))


number = int(input())

def rectangularGame(currentNum):
	if currentNum == 1:
		return 1
	else:
		numSqrt = int(currentNum ** 0.5)
		div = 1
		for i in range(2, numSqrt + 1):
			if currentNum % i == 0:
				div = i
				break
		if div == 1:
			return currentNum + 1
		else:
			return currentNum + rectangularGame(int(currentNum / div))
print(rectangularGame(number))


lower = 1
upper = 10 ** 9
n = int(input())
a = n
while n != 1:
	for num in range(lower, upper + 1):
		if num > 1:
			for i in range(2, num):
				if num % i == 0:
					break
			else:
				b = num
				if n % b == 0:
					a = a + int(n / b)
					n = int(n / b)
					break
print(a)


from math import sqrt
n = int(input())
sum = n
while n > 1:
	x = int(sqrt(n))
	true = 0
	for i in range(2, x + 1):
		if n % i == 0:
			true = 1
			break
	if true:
		n = int(n / i)
		sum += n
	else:
		break
sum += 1
print(sum)


from sys import *

def solve(n):
	i = 2
	s = n
	while i * i <= n:
		if n % i == 0:
			n = n // i
			s += n
		else:
			i += 1
	return s
	pass
test = 1
for t in range(0, test):
	n = int(input())
	ans = solve(n)
	print(ans + 1)


def pfs(n):
	p = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			p.append(i)
			n = n // i
		else:
			i += 1
	if n > 1:
		p.append(n)
	return p

def score(n):
	p = pfs(n)
	score = n
	for q in p:
		n = n // q
		score += n
	return score
n = int(input())
print(score(n))


import math
n = int(input())
x = n
numbers = [1 for i in range(x + 1)]
numbers[0] = 0
numbers[1] = 0
for i in range(2, x + 1):
	if numbers[i]:
		j = 2
		while j * i <= x:
			numbers[j * i] = 0
			j += 1
primes = []
for i in range(x + 1):
	if numbers[i]:
		primes.append(i)

def max_power(a, b):
	counter = 0
	while b % a == 0:
		counter += 1
		b /= a
	return counter
z = n
factorization = []
for prime in primes:
	x = max_power(prime, z)
	if x > 0:
		z /= prime ** x
		factorization.append((prime, x))
factorization.sort()
answer = n
for factor in factorization:
	prime = factor[0]
	power = factor[1]
	for i in range(power):
		n /= prime
		answer += n
print(int(answer))


from math import sqrt
n = int(input())
lim = int(sqrt(n))
i = 2
ans = n
while i <= lim:
	if n % i != 0:
		lim = int(sqrt(n))
		i += 1
	else:
		n = n // i
		ans += n
if n > 1:
	print(ans + 1)
else:
	print(ans)