You recently received a bag of chocolate sticks for Halloween. To prevent you from compulsively eating all the chocolate sticks in one go, your dietician devises the following fun game.

In each move, you choose one of the sticks from your bag. Then, you either eat it, or  break it into some number of equally-sized parts and save the pieces for later. The lengths of all sticks must always be integers, so breaking a stick into ${d}$ parts is possible only if ${d}$ is a divisor of the stick's length, and $d>1$.

Note that this means that a stick of length ${1}$ cannot be broken anymore, and can only be eaten.

For example, a chocolate stick of length ${4}$ will be dealt with as shown below. 

Given the chocolate sticks you received, determine the length of the longest sequence of moves you can perform.

Complete the function longestSequence which takes an integer array ${a}$, denoting the lengths of the chocolate sticks, as input. Return the maximum number of moves you can perform to consume the chocolate sticks according the game. 

Input Format

The first line contains one integer $n$ which is the number of chocolate sticks.

The second line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$, the lengths of the chocolate sticks.

Constraints

$1\leq n\leq100$
$1\leq a_i\leq10^{12}$

Subtasks  

For $20\%$ of the total score, $a_i\leq10^{6}$

Output Format

Print a single integer which is the maximum number of moves you can perform.

Sample Input 0
1
6

Sample Output 0
10

Explanation 0

You break a chocolate stick into three equal parts (1 move), then break each of them in half (3 moves), and then eat all six sticks (6 moves). This gives you 10 moves. 

Sample Input 1
3
1 7 24

Sample Output 1
55

Explanation 1

You make 1 move using the stick of length 1, then 8 moves using the stick of length 7, and in the end 46 moves using the stick of length 24. This gives 55 moves in total.

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
import sys
NPr = 10 ** 6 + 10
psieve = [True] * NPr
psieve[0] = False
psieve[1] = False
primes = []
for i in range(NPr):
	if psieve[i]:
		primes.append(i)
		for j in range(i, NPr, i):
			psieve[j] = False

def nmoves(x):
	pf = []
	y = x
	for p in primes:
		while x % p == 0:
			pf.append(p)
			x = x // p
		if x == 1 or p > x:
			break
	if x > 1:
		pf.append(x)
	ans = y
	for p in pf:
		y = y // p
		ans += y
	return ans

def longestSequence(a):
	return sum((nmoves(x) for x in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


from math import sqrt, ceil
from collections import defaultdict

def sieve(N):
	b = [True] * (N + 1)
	b[0] = False
	b[1] = False
	lim = ceil(sqrt(N))
	i = 2
	while i <= lim:
		if b[i]:
			for n in range(i ** 2, N + 1, i):
				b[n] = False
		i += 1
	return {i for (i, b) in enumerate(b) if b}

def factor(n, P):
	if n in P:
		return [n]
	f = []
	for p in P:
		while n % p == 0:
			n //= p
			f.append(p)
		if n in P:
			f.append(n)
			return f
	if n != 1:
		f.append(n)
	return f
P = sieve(10 ** 6 + 1)
n = int(input())
A = [int(x) for x in input().split()]
S = 0
for a in A:
	F = reversed(sorted(factor(a, P)))
	p = 1
	S += 1
	for f in F:
		p *= f
		S += p
print(S)


import sys

def get_primes(n):
	is_prime = [True] * (n + 1)
	rtn = []
	for i in range(2, n + 1):
		if not is_prime[i]:
			continue
		rtn.append(i)
		j = 2
		while i * j <= n:
			is_prime[i * j] = False
			j += 1
	return rtn

def longestSequence(a):
	cache = dict()
	primes = get_primes(1000000)

	def get_cache(n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n in cache:
			return cache[n]
		best_p = n
		for p in primes:
			if p >= n:
				break
			elif n % p == 0:
				best_p = p
				break
		rtn = n + get_cache(n // best_p)
		cache[n] = rtn
		return rtn
	if not a:
		return 0
	else:
		results = [get_cache(n) for n in a]
		return sum(results)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


from math import floor, sqrt
import sys

def eratosthenes(n):
	is_prime = [True] * ((n - 1) // 2)
	for p in range(3, floor(sqrt(n)) + 1, 2):
		if is_prime[(p - 3) // 2]:
			is_prime[(p ** 2 - 3) // 2::p] = [False] * ((n - p ** 2) // (2 * p) + 1)
	return [2] + [2 * i + 3 for i in range((n - 1) // 2) if is_prime[i]]

def longestSequence(a):
	primes = eratosthenes(10 ** 6 + 100)
	res = 0
	for val in a:
		res += val
		factors = []
		for p in primes:
			while val % p == 0:
				factors.append(p)
				val //= p
			if p ** 2 > val:
				if val > 1:
					factors.append(val)
				break
		mult = 1
		for p in factors[-1::-1]:
			res += mult
			mult *= p
	return res
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
from itertools import compress
from functools import lru_cache

def primes(n):
	sieve = bytearray([True]) * (n // 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = bytearray((n - i * i - 1) // (2 * i) + 1)
	return [2, *compress(range(3, n, 2), sieve[1:])]
primeslist = primes(10 ** 6 + 1)

def factorization(n):
	pf = []
	for p in primeslist:
		if p * p > n:
			break
		count = 0
		while not n % p:
			n //= p
			count += 1
		if count > 0:
			pf.append((p, count))
	if n > 1:
		pf.append((n, 1))
	return pf

def divisors(n):
	divs = [1]
	for (p, e) in factorization(n):
		divs += [x * p ** k for k in range(1, e + 1) for x in divs]
	return divs

@lru_cache(maxsize=None)
def f(a):
	if a == 1:
		return 1
	i = 0
	m = 0
	for d in divisors(a):
		if d == 1:
			continue
		m = max(m, 1 + d * f(a // d))
	return m

def longestSequence(a):
	return sum((f(x) for x in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


from math import sqrt, log2, ceil, floor, gcd
import random
import sys
from builtins import ValueError
MAX_DIGITS_POLLARD = 30
POLLARD_QUICK_ITERATIONS = 20
MIN_DIGITS_POLLARD_QUICK2 = 45
POLLARD_QUICK2_ITERATIONS = 25
SIQS_TRIAL_DIVISION_EPS = 25
SIQS_MIN_PRIME_POLYNOMIAL = 400
SIQS_MAX_PRIME_POLYNOMIAL = 4000
MILLER_RABIN_ITERATIONS = 50

class Polynomial:

	def __init__(self, coeff=[], a=None, b=None):
		self.coeff = coeff
		self.a = a
		self.b = b

	def eval(self, x):
		res = 0
		for a in self.coeff[::-1]:
			res *= x
			res += a
		return res

class FactorBasePrime:

	def __init__(self, p, tmem, lp):
		self.p = p
		self.soln1 = None
		self.soln2 = None
		self.tmem = tmem
		self.lp = lp
		self.ainv = None

def lowest_set_bit(a):
	b = a & -a
	low_bit = -1
	while b:
		b >>= 1
		low_bit += 1
	return low_bit

def to_bits(k):
	k_binary = bin(k)[2:]
	return (bit == '1' for bit in k_binary[::-1])

def pow_mod(a, k, m):
	r = 1
	b = a
	for bit in to_bits(k):
		if bit:
			r = r * b % m
		b = b * b % m
	return r

def is_quadratic_residue(a, p):
	return legendre(a, (p - 1) // 2, 1, p) == 1

def legendre(a, q, l, n):
	x = q ** l
	if x == 0:
		return 1
	z = 1
	a %= n
	while x != 0:
		if x % 2 == 0:
			a = a ** 2 % n
			x //= 2
		else:
			x -= 1
			z = z * a % n
	return z

def sqrt_mod_prime(a, p):
	assert a < p
	assert is_probable_prime(p)
	if a == 0:
		return 0
	if p == 2:
		return a
	if p % 2 == 0:
		return None
	p_mod_8 = p % 8
	if p_mod_8 == 1:
		q = p // 8
		e = 3
		while q % 2 == 0:
			q //= 2
			e += 1
		while True:
			x = random.randint(2, p - 1)
			z = pow_mod(x, q, p)
			if pow_mod(z, 2 ** (e - 1), p) != 1:
				break
		y = z
		r = e
		x = pow_mod(a, (q - 1) // 2, p)
		v = a * x % p
		w = v * x % p
		while True:
			if w == 1:
				return v
			k = 1
			while pow_mod(w, 2 ** k, p) != 1:
				k += 1
			d = pow_mod(y, 2 ** (r - k - 1), p)
			y = d ** 2 % p
			r = k
			v = d * v % p
			w = w * y % p
	elif p_mod_8 == 5:
		v = pow_mod(2 * a, (p - 5) // 8, p)
		i = 2 * a * v * v % p
		return a * v * (i - 1) % p
	else:
		return pow_mod(a, (p + 1) // 4, p)

def inv_mod(a, m):
	return eea(a, m)[0] % m

def eea(a, b):
	if a == 0:
		return (0, 1, b)
	x = eea(b % a, a)
	return (x[1] - b // a * x[0], x[0], x[2])

def is_probable_prime(a):
	if a == 2:
		return True
	if a == 1 or a % 2 == 0:
		return False
	return primality_test_miller_rabin(a, MILLER_RABIN_ITERATIONS)

def primality_test_miller_rabin(a, iterations):
	m = a - 1
	lb = lowest_set_bit(m)
	m >>= lb
	for _ in range(iterations):
		b = random.randint(2, a - 1)
		j = 0
		z = pow_mod(b, m, a)
		while not (j == 0 and z == 1 or z == a - 1):
			if j > 0 and z == 1 or j + 1 == lb:
				return False
			j += 1
			z = z * z % a
	return True

def siqs_factor_base_primes(n, nf):
	global small_primes
	factor_base = []
	for p in small_primes:
		if is_quadratic_residue(n, p):
			t = sqrt_mod_prime(n % p, p)
			lp = round(log2(p))
			factor_base.append(FactorBasePrime(p, t, lp))
			if len(factor_base) >= nf:
				break
	return factor_base

def siqs_find_first_poly(n, m, factor_base):
	p_min_i = None
	p_max_i = None
	for (i, fb) in enumerate(factor_base):
		if p_min_i is None and fb.p >= SIQS_MIN_PRIME_POLYNOMIAL:
			p_min_i = i
		if p_max_i is None and fb.p > SIQS_MAX_PRIME_POLYNOMIAL:
			p_max_i = i - 1
			break
	if p_max_i is None:
		p_max_i = len(factor_base) - 1
	if p_min_i is None or p_max_i - p_min_i < 20:
		p_min_i = min(p_min_i, 5)
	target = sqrt(2 * float(n)) / m
	target1 = target / ((factor_base[p_min_i].p + factor_base[p_max_i].p) / 2) ** 0.5
	(best_q, best_a, best_ratio) = (None, None, None)
	for _ in range(30):
		a = 1
		q = []
		while a < target1:
			p_i = 0
			while p_i == 0 or p_i in q:
				p_i = random.randint(p_min_i, p_max_i)
			p = factor_base[p_i].p
			a *= p
			q.append(p_i)
		ratio = a / target
		if best_ratio is None or (ratio >= 0.9 and ratio < best_ratio) or (best_ratio < 0.9 and ratio > best_ratio):
			best_q = q
			best_a = a
			best_ratio = ratio
	a = best_a
	q = best_q
	s = len(q)
	B = []
	for l in range(s):
		fb_l = factor_base[q[l]]
		q_l = fb_l.p
		assert a % q_l == 0
		gamma = fb_l.tmem * inv_mod(a // q_l, q_l) % q_l
		if gamma > q_l // 2:
			gamma = q_l - gamma
		B.append(a // q_l * gamma)
	b = sum(B) % a
	b_orig = b
	if 2 * b > a:
		b = a - b
	assert 0 < b
	assert 2 * b <= a
	assert (b * b - n) % a == 0
	g = Polynomial([b * b - n, 2 * a * b, a * a], a, b_orig)
	h = Polynomial([b, a])
	for fb in factor_base:
		if a % fb.p != 0:
			fb.ainv = inv_mod(a, fb.p)
			fb.soln1 = fb.ainv * (fb.tmem - b) % fb.p
			fb.soln2 = fb.ainv * (-fb.tmem - b) % fb.p
	return (g, h, B)

def siqs_find_next_poly(n, factor_base, i, g, B):
	v = lowest_set_bit(i) + 1
	z = -1 if ceil(i / 2 ** v) % 2 == 1 else 1
	b = (g.b + 2 * z * B[v - 1]) % g.a
	a = g.a
	b_orig = b
	if 2 * b > a:
		b = a - b
	assert (b * b - n) % a == 0
	g = Polynomial([b * b - n, 2 * a * b, a * a], a, b_orig)
	h = Polynomial([b, a])
	for fb in factor_base:
		if a % fb.p != 0:
			fb.soln1 = fb.ainv * (fb.tmem - b) % fb.p
			fb.soln2 = fb.ainv * (-fb.tmem - b) % fb.p
	return (g, h)

def siqs_sieve(factor_base, m):
	sieve_array = [0] * (2 * m + 1)
	for fb in factor_base:
		if fb.soln1 is None:
			continue
		p = fb.p
		i_start_1 = -((m + fb.soln1) // p)
		a_start_1 = fb.soln1 + i_start_1 * p
		lp = fb.lp
		if p > 20:
			for a in range(a_start_1 + m, 2 * m + 1, p):
				sieve_array[a] += lp
			i_start_2 = -((m + fb.soln2) // p)
			a_start_2 = fb.soln2 + i_start_2 * p
			for a in range(a_start_2 + m, 2 * m + 1, p):
				sieve_array[a] += lp
	return sieve_array

def siqs_trial_divide(a, factor_base):
	divisors_idx = []
	for (i, fb) in enumerate(factor_base):
		if a % fb.p == 0:
			exp = 0
			while a % fb.p == 0:
				a //= fb.p
				exp += 1
			divisors_idx.append((i, exp))
		if a == 1:
			return divisors_idx
	return None

def siqs_trial_division(n, sieve_array, factor_base, smooth_relations, g, h, m, req_relations):
	sqrt_n = sqrt(float(n))
	limit = log2(m * sqrt_n) - SIQS_TRIAL_DIVISION_EPS
	for (i, sa) in enumerate(sieve_array):
		if sa >= limit:
			x = i - m
			gx = g.eval(x)
			divisors_idx = siqs_trial_divide(gx, factor_base)
			if divisors_idx is not None:
				u = h.eval(x)
				v = gx
				assert u * u % n == v % n
				smooth_relations.append((u, v, divisors_idx))
				if len(smooth_relations) >= req_relations:
					return True
	return False

def siqs_build_matrix(factor_base, smooth_relations):
	fb = len(factor_base)
	M = []
	for sr in smooth_relations:
		mi = [0] * fb
		for (j, exp) in sr[2]:
			mi[j] = exp % 2
		M.append(mi)
	return M

def siqs_build_matrix_opt(M):
	m = len(M[0])
	cols_binary = [''] * m
	for mi in M:
		for (j, mij) in enumerate(mi):
			cols_binary[j] += '1' if mij else '0'
	return ([int(cols_bin[::-1], 2) for cols_bin in cols_binary], len(M), m)

def add_column_opt(M_opt, tgt, src):
	M_opt[tgt] ^= M_opt[src]

def find_pivot_column_opt(M_opt, j):
	if M_opt[j] == 0:
		return None
	return lowest_set_bit(M_opt[j])

def siqs_solve_matrix_opt(M_opt, n, m):
	row_is_marked = [False] * n
	pivots = [-1] * m
	for j in range(m):
		i = find_pivot_column_opt(M_opt, j)
		if i is not None:
			pivots[j] = i
			row_is_marked[i] = True
			for k in range(m):
				if k != j and M_opt[k] >> i & 1:
					add_column_opt(M_opt, k, j)
	perf_squares = []
	for i in range(n):
		if not row_is_marked[i]:
			perfect_sq_indices = [i]
			for j in range(m):
				if M_opt[j] >> i & 1:
					perfect_sq_indices.append(pivots[j])
			perf_squares.append(perfect_sq_indices)
	return perf_squares

def siqs_calc_sqrts(square_indices, smooth_relations):
	res = [1, 1]
	for idx in square_indices:
		res[0] *= smooth_relations[idx][0]
		res[1] *= smooth_relations[idx][1]
	res[1] = sqrt_int(res[1])
	return res

def sqrt_int(n):
	a = n
	s = 0
	o = 1 << (floor(log2(n)) & ~1)
	while o != 0:
		t = s + o
		if a >= t:
			a -= t
			s = (s >> 1) + o
		else:
			s >>= 1
		o >>= 2
	assert s * s == n
	return s

def kth_root_int(n, k):
	u = n
	s = n + 1
	while u < s:
		s = u
		t = (k - 1) * s + n // pow(s, k - 1)
		u = t // k
	return s

def siqs_factor_from_square(n, square_indices, smooth_relations):
	(sqrt1, sqrt2) = siqs_calc_sqrts(square_indices, smooth_relations)
	assert sqrt1 * sqrt1 % n == sqrt2 * sqrt2 % n
	return gcd(abs(sqrt1 - sqrt2), n)

def siqs_find_factors(n, perfect_squares, smooth_relations):
	factors = []
	rem = n
	non_prime_factors = set()
	prime_factors = set()
	for square_indices in perfect_squares:
		fact = siqs_factor_from_square(n, square_indices, smooth_relations)
		if fact != 1 and fact != rem:
			if is_probable_prime(fact):
				if fact not in prime_factors:
					prime_factors.add(fact)
				while rem % fact == 0:
					factors.append(fact)
					rem //= fact
				if rem == 1:
					break
				if is_probable_prime(rem):
					factors.append(rem)
					rem = 1
					break
			elif fact not in non_prime_factors:
				non_prime_factors.add(fact)
	if rem != 1 and non_prime_factors:
		non_prime_factors.add(rem)
		for fact in sorted(siqs_find_more_factors_gcd(non_prime_factors)):
			while fact != 1 and rem % fact == 0:
				factors.append(fact)
				rem //= fact
			if rem == 1 or is_probable_prime(rem):
				break
	if rem != 1:
		factors.append(rem)
	return factors

def siqs_find_more_factors_gcd(numbers):
	res = set()
	for n in numbers:
		res.add(n)
		for m in numbers:
			if n != m:
				fact = gcd(n, m)
				if fact != 1 and fact != n and (fact != m):
					if fact not in res:
						res.add(fact)
					res.add(n // fact)
					res.add(m // fact)
	return res

def siqs_choose_nf_m(d):
	if d <= 34:
		return (200, 65536)
	if d <= 36:
		return (300, 65536)
	if d <= 38:
		return (400, 65536)
	if d <= 40:
		return (500, 65536)
	if d <= 42:
		return (600, 65536)
	if d <= 44:
		return (700, 65536)
	if d <= 48:
		return (1000, 65536)
	if d <= 52:
		return (1200, 65536)
	if d <= 56:
		return (2000, 65536 * 3)
	if d <= 60:
		return (4000, 65536 * 3)
	if d <= 66:
		return (6000, 65536 * 3)
	if d <= 74:
		return (10000, 65536 * 3)
	if d <= 80:
		return (30000, 65536 * 3)
	if d <= 88:
		return (50000, 65536 * 3)
	if d <= 94:
		return (60000, 65536 * 9)
	return (100000, 65536 * 9)

def siqs_factorise(n):
	dig = len(str(n))
	(nf, m) = siqs_choose_nf_m(dig)
	factor_base = siqs_factor_base_primes(n, nf)
	required_relations_ratio = 1.05
	success = False
	smooth_relations = []
	prev_cnt = 0
	i_poly = 0
	while not success:
		required_relations = round(len(factor_base) * required_relations_ratio)
		enough_relations = False
		while not enough_relations:
			if i_poly == 0:
				(g, h, B) = siqs_find_first_poly(n, m, factor_base)
			else:
				(g, h) = siqs_find_next_poly(n, factor_base, i_poly, g, B)
			i_poly += 1
			if i_poly >= 2 ** (len(B) - 1):
				i_poly = 0
			sieve_array = siqs_sieve(factor_base, m)
			enough_relations = siqs_trial_division(n, sieve_array, factor_base, smooth_relations, g, h, m, required_relations)
			if len(smooth_relations) >= required_relations or (i_poly % 8 == 0 and len(smooth_relations) > prev_cnt):
				prev_cnt = len(smooth_relations)
		M = siqs_build_matrix(factor_base, smooth_relations)
		(M_opt, M_n, M_m) = siqs_build_matrix_opt(M)
		perfect_squares = siqs_solve_matrix_opt(M_opt, M_n, M_m)
		factors = siqs_find_factors(n, perfect_squares, smooth_relations)
		if len(factors) > 1:
			success = True
		else:
			required_relations_ratio += 0.05
	return factors

def check_factor(n, i, factors):
	while n % i == 0:
		n //= i
		factors.append(i)
		if is_probable_prime(n):
			factors.append(n)
			n = 1
	return n

def trial_div_init_primes(n, upper_bound):
	global small_primes
	is_prime = [True] * (upper_bound + 1)
	is_prime[0:2] = [False] * 2
	factors = []
	small_primes = []
	max_i = sqrt_int(upper_bound)
	rem = n
	for i in range(2, max_i + 1):
		if is_prime[i]:
			small_primes.append(i)
			rem = check_factor(rem, i, factors)
			if rem == 1:
				return (factors, 1)
			for j in range(i ** 2, upper_bound + 1, i):
				is_prime[j] = False
	for i in range(max_i + 1, upper_bound + 1):
		if is_prime[i]:
			small_primes.append(i)
			rem = check_factor(rem, i, factors)
			if rem == 1:
				return (factors, 1)
	return (factors, rem)

def pollard_brent_f(c, n, x):
	x1 = x * x % n + c
	if x1 >= n:
		x1 -= n
	assert x1 >= 0 and x1 < n
	return x1

def pollard_brent_find_factor(n, max_iter=None):
	(y, c, m) = (random.randint(1, n - 1) for _ in range(3))
	(r, q, g) = (1, 1, 1)
	i = 0
	while g == 1:
		x = y
		for _ in range(r):
			y = pollard_brent_f(c, n, y)
		k = 0
		while k < r and g == 1:
			ys = y
			for _ in range(min(m, r - k)):
				y = pollard_brent_f(c, n, y)
				q = q * abs(x - y) % n
			g = gcd(q, n)
			k += m
		r *= 2
		if max_iter:
			i += 1
			if i == max_iter:
				return None
	if g == n:
		while True:
			ys = pollard_brent_f(c, n, ys)
			g = gcd(abs(x - ys), n)
			if g > 1:
				break
	return g

def pollard_brent_quick(n, factors):
	rem = n
	while True:
		if is_probable_prime(rem):
			factors.append(rem)
			rem = 1
			break
		digits = len(str(n))
		if digits < MIN_DIGITS_POLLARD_QUICK2:
			max_iter = POLLARD_QUICK_ITERATIONS
		else:
			max_iter = POLLARD_QUICK2_ITERATIONS
		f = pollard_brent_find_factor(rem, max_iter)
		if f and f < rem:
			if is_probable_prime(f):
				factors.append(f)
				assert rem % f == 0
				rem //= f
			else:
				rem_f = pollard_brent_quick(f, factors)
				rem = rem // f * rem_f
		else:
			break
	return rem

def check_perfect_power(n):
	largest_checked_prime = small_primes[-1]
	for b in small_primes:
		bth_root = kth_root_int(n, b)
		if bth_root < largest_checked_prime:
			break
		if bth_root ** b == n:
			return (bth_root, b)
	return None

def find_prime_factors(n):
	perfect_power = check_perfect_power(n)
	if perfect_power:
		factors = [perfect_power[0]]
	else:
		digits = len(str(n))
		if digits <= MAX_DIGITS_POLLARD:
			factors = [pollard_brent_find_factor(n)]
		else:
			factors = siqs_factorise(n)
	prime_factors = []
	for f in set(factors):
		for pf in find_all_prime_factors(f):
			prime_factors.append(pf)
	return prime_factors

def find_all_prime_factors(n):
	rem = n
	factors = []
	while rem > 1:
		if is_probable_prime(rem):
			factors.append(rem)
			break
		for f in find_prime_factors(rem):
			assert is_probable_prime(f)
			assert rem % f == 0
			while rem % f == 0:
				rem //= f
				factors.append(f)
	return factors

def product(factors):
	prod = 1
	for f in factors:
		prod *= f
	return prod

def factorise(n):
	if type(n) != int or n < 1:
		raise ValueError('Number needs to be an integer >= 1')
	if n == 1:
		return []
	if is_probable_prime(n):
		return [n]
	(factors, rem) = trial_div_init_primes(n, 1000000)
	if rem != 1:
		digits = len(str(rem))
		if digits > MAX_DIGITS_POLLARD:
			rem = pollard_brent_quick(rem, factors)
		if rem > 1:
			for fr in find_all_prime_factors(rem):
				factors.append(fr)
	factors.sort()
	assert product(factors) == n
	for p in factors:
		assert is_probable_prime(p)
	return factors
x = int(input())
l = list(map(int, input().strip().split()))
cnt2 = sum(l)
for N in l:
	for i in factorise(N):
		N = N // i
		cnt2 += N
print(cnt2)


def factors(n):
	gaps = [1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6]
	(length, cycle) = (11, 3)
	(f, fs, next) = (2, [], 0)
	while f * f <= n:
		while n % f == 0:
			fs.append(int(f))
			n /= f
		f += gaps[next]
		next += 1
		if next == length:
			next = cycle
	if n > 1:
		fs.append(int(n))
	return fs

def longSequence(num):
	nlist = factors(num)
	nlist.reverse()
	level = 1
	sum = 1
	for i in nlist:
		level = level * i
		sum += level
	return sum

def longestSequence(a):
	count = 0
	for i in a:
		count += longSequence(i)
	return count
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

def primeFactors(n):
	res = []
	while n % 2 == 0:
		res.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			res.append(i)
			n = n / i
	if n > 2:
		res.append(n)
	return res

def longestSequence(a):
	length = []
	for n in a:
		move = 1
		pieces = 1
		size = n
		factors = primeFactors(n)
		factors.reverse()
		for f in factors:
			pieces *= f
			size /= f
			move += pieces
		length.append(move)
	return int(sum(length))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

def get_moves(c):
	if c == 1:
		return 1
	if c % 2 == 0:
		return c + get_moves(c // 2)
	for i in range(3, math.floor(math.sqrt(c)) + 1, 2):
		if c % i == 0:
			return c + get_moves(c // i)
	return c + 1

def longestSequence(a):
	total = 0
	for c in a:
		total += get_moves(c)
	return total
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
from math import sqrt

def factors(n):
	j = 3
	while n > 1:
		while n & 1 == 0:
			yield n
			n //= 2
		for i in range(j, int(sqrt(n + 0.05)) + 1, 2):
			if n % i == 0:
				j = i
				yield n
				n //= i
				break
		else:
			if n > 1:
				yield n
				break

def longestSequence(a):
	moves = 0
	for stick in a:
		moves += 1
		for factor in factors(stick):
			moves += factor
	return moves
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def minDivisor(x):
	if x % 2 == 0:
		return 2
	else:
		for i in range(3, int(x ** 0.5 + 1), 2):
			if x % i == 0:
				return i
	return x

def findDivisors(x):
	res = [1]
	while True:
		divisor = minDivisor(x)
		if divisor == 1:
			break
		res.append(divisor)
		x = x // divisor
	return res

def countForOne(x):
	steps = 0
	divisors = findDivisors(x)
	for d in divisors:
		x = x // d
		steps += x
	return steps

def longestSequence(a):
	return int(sum((countForOne(x) for x in a)))
sys.setrecursionlimit(10000)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys, math

def prime_factors(n):
	primes = []
	while n % 2 == 0:
		primes.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			primes.append(i)
			n = n // i
	if n > 2:
		primes.append(n)
	return primes

def longestSequence(a):
	total = 0
	for stick in a:
		moves = 1
		total += moves
		p = prime_factors(stick)
		p.sort(reverse=True)
		for i in range(0, len(p)):
			moves *= p[i]
			total += moves
	return total
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import itertools
import math
memo = {}

def prime_factorization(n):
	res = []
	while n > 1:
		for i in itertools.chain([2], range(3, int(math.sqrt(n)) + 1, 2), [n]):
			if n % i == 0:
				res.append(i)
				n //= i
				break
	return res

def max_moves(stick_len, factorization=None):
	if stick_len in memo:
		return memo[stick_len]
	if factorization is None:
		factorization = prime_factorization(stick_len)
	if len(factorization) == 0:
		return 1
	div = factorization.pop()
	moves = 1 + div * max_moves(stick_len // div, factorization=factorization)
	memo[stick_len] = moves
	return moves

def longestSequence(a):
	result = 0
	for stick in a:
		result += max_moves(stick)
	return result
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


from math import sqrt

def divisor(n):
	if n % 2 == 0:
		return n // 2
	for i in range(3, int(sqrt(n) + 1), 2):
		if n % i == 0:
			return n // i
	return 1

def longestSequence(a):
	sum = 0
	for n in a:
		while n > 1:
			sum += n
			n = divisor(n)
		sum += 1
	return sum
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math
from functools import lru_cache

def find_max_prime_factor(size):
	while size % 2 == 0:
		max_prime = 2
		size //= 2
	for i in range(3, math.floor(math.sqrt(size)) + 1, 2):
		while size % i == 0:
			max_prime = i
			size //= i
	if size > 2:
		max_prime = size
	return max_prime

def longestSequence(a):

	@lru_cache(maxsize=None)
	def helper(size):
		if size == 1:
			return 1
		max_prime_factor = find_max_prime_factor(size)
		res = 1 + max_prime_factor * helper(size // max_prime_factor)
		return res
	total = 0
	for i in a:
		total += helper(i)
	return total
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

def factorize_number(number):
	res = []
	count = 0
	while number % 2 == 0:
		count += 1
		number //= 2
	if count > 0:
		res.append((2, count))
	for i in range(3, int(math.sqrt(number) + 2), 2):
		if i > number:
			break
		count = 0
		while number % i == 0:
			count += 1
			number //= i
		if count > 0:
			res.append((i, count))
	if number > 1:
		res.append((number, 1))
	return res

def longestSequence(n):
	res = factorize_number(n)
	res = res[::-1]
	result = 0
	sofar = 1
	for i in range(len(res)):
		for j in range(res[i][1]):
			result += sofar
			sofar *= res[i][0]
	result += n
	return result
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = 0
for i in range(n):
	result += longestSequence(a[i])
print(result)


from functools import lru_cache
import sys
pmax = 10 ** 6
P = 2 * [False] + (pmax - 1) * [True]
for i in range(2, int(pmax ** 0.5) + 1):
	if P[i]:
		for j in range(i ** 2, pmax + 1, i):
			P[j] = False
primes = [i for i in range(2, pmax + 1) if P[i]]

@lru_cache(maxsize=None)
def count(a):
	if a == 1:
		return 1
	for p in primes:
		if not a % p:
			return a + count(a // p)
	return a + 1

def longestSequence(A):
	return sum((count(a) for a in A))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def func(n):
	if n == 1:
		return 1
	div_list = []
	i = 2
	while n % 2 == 0:
		n //= 2
		div_list.append(2)
	i = 3
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
				div_list.append(i)
		i += 2
	if n != 1:
		div_list.append(n)
		n = 1
	if len(div_list) == 1:
		return 1 + div_list[0]
	res = 0
	factor = 1
	div_list.reverse()
	for idx in range(len(div_list)):
		res += factor
		factor *= div_list[idx]
	return res + factor

def longestSequence(a):
	total = 0
	for el in a:
		total += func(el)
	return total
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
for i in range(2, 1000):
	for p in primes:
		if i % p == 0:
			break
	else:
		primes.append(i)
for i in range(1000, 1000000):
	for p in primes:
		if i % p == 0:
			break
		elif p > 1000:
			primes.append(i)
			break
	else:
		primes.append(i)

def sub(num):
	for p in primes:
		if num % p == 0:
			return num + sub(num // p)
	if num == 1:
		return 1
	else:
		return num + 1

def longestSequence(a):
	return sum([sub(num) for num in a])
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def rwh_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = rwh_primes(int(2000000.0))
plen = len(primes)

def count(a):
	ans = a = int(a)
	if a == 1:
		return 1
	i = 0
	while a > 1:
		p = primes[i]
		if p * p > a:
			ans += 1
			break
		while a % p == 0:
			a //= p
			ans += a
		i += 1
	return ans
n = int(input().strip())
print(sum(map(count, input().strip().split())))


import re
import sys

def highest_odd_factor(n):
	wheel = [1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6]
	(w, f, fs) = (0, 2, [])
	while f * f <= n:
		while n % f == 0:
			fs.append(f)
			n //= f
		(f, w) = (f + wheel[w], w + 1)
		if w == 11:
			w = 3
	if n > 1:
		fs.append(n)
	if not fs:
		return None
	else:
		return fs[-1]
lines = [line.strip() for line in sys.stdin.readlines()]
lengths = [int(length) for length in re.split('[^\\d]', lines[1])]
totalmoves = 0
for length in lengths:
	full_length = length
	pieces = 1
	moves = 0
	while True:
		factor = highest_odd_factor(length)
		if factor:
			moves += pieces
			length //= factor
			pieces = full_length // length
		else:
			break
	while length % 2 == 0:
		moves += pieces
		length //= 2
		pieces = full_length // length
	if length != 1:
		moves += pieces
	totalmoves += moves + full_length
print(totalmoves)


import sys
import math

def longestSequence(a):
	moves = 0
	for choc in a:
		pieces = 1
		size = choc
		divisors = []
		while size % 2 == 0:
			divisors.append(2)
			size = int(size / 2)
		start = 3
		while size > 1:
			sqch = int(math.sqrt(size))
			ended = True
			for i in range(start, sqch + 1, 2):
				if size % i == 0:
					divisors.append(i)
					size = int(size / i)
					start = i
					ended = False
					break
			if ended:
				divisors.append(size)
				size = 1
		while divisors:
			moves += pieces
			pieces *= divisors.pop()
		moves += pieces
	return moves
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


cache = {}

def sieve(n):
	if n <= 2:
		return []
	sieve = list(range(3, n, 2))
	top = len(sieve)
	for si in sieve:
		if si:
			bottom = (si * si - 3) // 2
			if bottom >= top:
				break
			sieve[bottom::si] = [0] * -((bottom - top) // si)
	return [2] + [el for el in sieve if el]
k_max = 10000000
k_list = sieve(k_max)

def get_moves(n):
	if n not in cache:
		if n == 1:
			cache[n] = 0
			return cache[n]
		for i in k_list:
			if n % i == 0:
				moves = int(n / i)
				cache[n] = moves + get_moves(moves)
				return cache[n]
		n_lim = int(n ** 0.5)
		for i in range(k_max + 1, n_lim, 2):
			if n % i == 0:
				moves = int(n / i)
				cache[n] = moves + get_moves(moves)
				return cache[n]
		cache[n] = 1
	return cache[n]

def longestSequence(a):
	total_moves = 0
	a = sorted(a)
	for i in a:
		total_moves = total_moves + i + get_moves(i)
	return total_moves
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def is_prime(n):
	n = abs(int(n))
	if n < 2:
		return True
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def calculate_moves(n):
	if n % 2 == 0:
		return n + calculate_moves(n / 2)
	elif is_prime(n):
		if n == 1:
			return 1
		return 1 + n
	else:
		diviser = 1
		for i in range(3, int(n ** 0.5) + 1):
			if n % i == 0:
				diviser = i
				break
		return n + calculate_moves(n / diviser)

def longestSequence(a):
	sum_moves = 0
	for n in a:
		moves_of_number = calculate_moves(n)
		sum_moves += moves_of_number
	return sum_moves
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(int(result))


import sys

def getprimes():
	p = [1] * int(1000000.0 + 1)
	p[3] = 1
	i = 3
	while i * i <= 1000000000000.0:
		if p[i] == 1:
			j = i * i
			while j * j <= 1000000000000.0:
				p[j] = 0
				j += i
		i += 2
	pp = [2]
	for i in range(3, len(p), 2):
		if p[i] == 1:
			pp.append(i)
	return pp

def getval(n, p, h):
	if n in h:
		return h[n]
	m = n
	nn = n
	p_i = 0
	pr = p[p_i]
	while nn > 1 and p_i < len(p):
		while nn % pr != 0:
			p_i += 1
			if p_i == len(p):
				pr = nn
				break
			pr = p[p_i]
		nn = nn // pr
		m += nn
	h[n] = m
	return m

def longestSequence(a, p):
	s = 0
	h = {}
	for i in a:
		s += getval(i, p, h)
	return s
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
p = getprimes()
result = longestSequence(a, p)
print(result)


import math
import sys

def primeFact(a):
	arr = []
	while a % 2 == 0:
		arr.append(2)
		a = a / 2
	for i in range(3, int(math.sqrt(a)) + 1, 2):
		while a % i == 0:
			arr.append(int(i))
			a = a / i
	if a > 2:
		arr.append(int(a))
	return arr

def longForAll(key):
	if key == 1:
		return 1
	arr = primeFact(key)
	arr = sorted(arr, key=lambda item: item, reverse=True)
	val = [arr[0]]
	for i in range(1, len(arr)):
		val.append(val[-1] * arr[i])
	return sum(val) + 1

def longestSequence(a):
	val = 0
	for i in range(0, len(a)):
		val += longForAll(a[i])
	return val
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


from random import randint
from fractions import gcd
import sys

def is_prime(n):
	k = int(1000 + n ** 0.25)
	if n <= 1 or n == 4:
		return 0
	if n <= 3:
		return 1
	while k > 0:
		a = 2 + randint(0, n - 3)
		if pow(a, n - 1, n) != 1:
			return 0
		k -= 1
	return 1

def rho(n):
	if n % 2 == 0:
		return 2
	if is_prime(n):
		return n
	while True:
		c = randint(2, n - 1)
		f = lambda x: x ** 2 + c
		x = y = 2
		d = 1
		while d == 1:
			x = f(x) % n
			y = f(f(y)) % n
			d = gcd((x - y) % n, n)
		if d != n:
			return d

def Div(a, d):
	if a > 1:
		r = rho(a)
		if is_prime(r):
			d.append(r)
		else:
			Div(r, d)
		Div(int(a / r), d)

def F(a):
	if a == 1:
		return 1
	if is_prime(a):
		return a + 1
	d = []
	Div(a, d)
	d = sorted(d)
	sum = 0
	for i in d:
		sum = (sum + 1) * i
	return 1 + sum
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
sum = 0
for i in a:
	sum += F(i)
print(sum)


import math
from functools import reduce

def primes_upto(n):
	sieve = [True] * n
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if sieve[i]:
			sieve[i * i::i + i] = [False] * ((n - i * i - 1) // (i + i) + 1)
	return [2] + list((i for i in range(3, n, 2) if sieve[i]))
primes = primes_upto(1000000)
primes_set = set(primes)

def factors(n):
	if n == 1:
		return
	for p in primes:
		if n % p == 0:
			while n % p == 0:
				yield p
				n //= p
			if n == 1:
				return
			elif n in primes_set:
				yield n
				return
	yield n

def longestSequence(a):
	return sum((reduce(lambda x, y: x * y + 1, factors(n), 1) for n in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def longestSequence(a):
	ans = 0
	for i in a:
		ans += 1
		arr1 = {}
		num = i
		for k in l:
			if k > num:
				arr1[num] = 1
				num = 1
				break
			elif num % k == 0:
				c = 0
				while num % k == 0:
					c += 1
					num = num // k
				arr1[k] = c
		if num != 1:
			arr1[num] = 1
			num = 1
		l1 = arr1.keys()
		l1 = sorted(l1, reverse=True)
		num1 = 1
		for j in l1:
			if j == 1:
				break
			for k in range(arr1[j]):
				ans += num * j
				num *= j
	return ans
arr = [0] * 1000000
l = []
for i in range(2, 50000):
	if arr[i] == 0:
		for j in range(2 * i, 50000, i):
			arr[j] = 1
		l.append(i)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


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

def solve(n):
	if n == 1:
		return 1
	else:
		cur = 1
		res = 1
		factor = prime_factors(n)
		for i in factor[::-1]:
			cur *= i
			res += cur
		return res
t = int(input())
inp = [int(i) for i in input().split()]
s = 0
for i in inp:
	s += solve(i)
print(s)


import random

def isPrime(p):
	if p <= 1:
		return False
	if p <= 3:
		return True
	if p % 2 == 0:
		return False
	s = p - 1
	while s % 2 == 0:
		s //= 2
	for i in range(4):
		a = random.randint(1, p - 1)
		x = pow(a, s, p)
		t = s
		while x != p - 1 and x != 1 and (t != p - 1):
			x = pow(x, 2, p)
			t *= 2
		if x != p - 1 and t % 2 == 0:
			return False
	return True

def getDiv(a):
	if isPrime(a):
		return 1
	i = 2
	while i * i <= a:
		if a % i == 0:
			return i
		i += 1
	return 1
res = 0
n = int(input())
arr = list(map(int, input().split()))
dp = {}
for a in arr:
	if a in dp:
		max_div = dp[a]
	else:
		max_div = getDiv(a)
		dp[a] = max_div
	x = a // max_div
	while max_div != 1:
		res += x
		if x in dp:
			max_div = dp[x]
		else:
			max_div = getDiv(x)
			dp[x] = max_div
		x //= max_div
	res += a + (a != 1)
print(res)


from math import sqrt
from math import floor
from bisect import bisect_left

def eratosthenes2(n):
	multiples = set()
	for i in range(2, n + 1):
		if i not in multiples:
			yield i
			multiples.update(range(i * i, n + 1, i))
	return multiples
__primes = list(eratosthenes2(31622))

def is_prime(n):
	if n <= 31622:
		i = bisect_left(__primes, n)
		return i != len(__primes) and __primes[i] == n
	limit = int(n ** 0.5)
	for p in __primes:
		if p > limit:
			return True
		if n % p == 0:
			return False
	for f in range(31627, limit, 6):
		if n % f == 0 or n % (f + 4) == 0:
			return False
	return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	else:
		squareRootOfn = int(floor(sqrt(n)))
		for i in range(3, squareRootOfn + 1, 2):
			if n % i == 0:
				return i

def find_moves(num):
	if num == 1:
		return 1
	if is_prime(num):
		return num + 1
	total = 0
	while num != 1 and (not is_prime(num)):
		total += num
		num //= smallestDivisor(num)
	return total + 1 + num

def longestSequence(a):
	su = 0
	for item in a:
		su += find_moves(item)
	return su
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def primes(n):
	(ps, sieve) = ([], [True] * (n + 1))
	for p in range(2, n + 1):
		if sieve[p]:
			ps.append(p)
			for i in range(p * p, n + 1, p):
				sieve[i] = False
	return ps
prime_data = primes(1000000)
n = int(input())
data = list(map(int, input().split()))
ans = 0
for no in data:
	var = 0
	ans += no
	try:
		while no != 1:
			while no % prime_data[var] == 0:
				no //= prime_data[var]
				ans += no
			var += 1
	except:
		ans += 1
print(ans)


import sys
import math

def longestSequence(a):
	total_moves = 0
	for stick in a:
		factors = prime_factors(stick)
		moves = 1
		prod = 1
		for f in reversed(factors):
			prod = prod * int(f)
			moves += prod
		total_moves += moves
	return total_moves

def prime_factors(n):
	factors = []
	d = 2
	sqrt_n = int(math.sqrt(n))
	while n > 1:
		while n % d == 0:
			factors.append(d)
			n //= d
		if d == 2:
			d += 1
		else:
			d += 2
		if d > sqrt_n:
			if n > 1:
				factors.append(n)
			break
	return factors
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import math

def primeFactors(n):
	p = []
	while n % 2 == 0:
		p.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			p.append(i)
			n = n // i
	if n > 2:
		p.append(n)
	return p
n = int(input())
choc = list(map(int, input().split()))
s = 0

def seq(n):
	if n == 1:
		return 1
	else:
		prime = primeFactors(n)
		prime.sort(reverse=True)
		ans = 1
		add = 1
		for i in range(len(prime)):
			add *= prime[i]
			ans += add
		return ans
for org in choc:
	s += seq(org)
print(s)


import sys
from random import randrange

def primesbelow(N):
	correction = N % 6 > 1
	N = {0: N, 1: N - 1, 2: N + 4, 3: N + 3, 4: N + 2, 5: N + 1}[N % 6]
	sieve = [True] * (N // 3)
	sieve[0] = False
	for i in range(int(N ** 0.5) // 3 + 1):
		if sieve[i]:
			k = 3 * i + 1 | 1
			sieve[k * k // 3::2 * k] = [False] * ((N // 6 - k * k // 6 - 1) // k + 1)
			sieve[(k * k + 4 * k - 2 * k * (i % 2)) // 3::2 * k] = [False] * ((N // 6 - (k * k + 4 * k - 2 * k * (i % 2)) // 6 - 1) // k + 1)
	return [2, 3] + [3 * i + 1 | 1 for i in range(1, N // 3 - correction) if sieve[i]]
smallprimes = primesbelow(1000001)
dp = {}
for s in smallprimes:
	dp[s] = True

def is_prime(n, k=10):
	if n in dp:
		return True
	if n == 2:
		return True
	if not n & 1:
		return False

	def check(a, s, d, n):
		x = pow(a, d, n)
		if x == 1:
			return True
		for i in range(s - 1):
			if x == n - 1:
				return True
			x = pow(x, 2, n)
		return x == n - 1
	s = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		s += 1
	for i in range(k):
		a = randrange(2, n - 1)
		if not check(a, s, d, n):
			return False
	return True

def primefactors(n, sort=False):
	factors = []
	for checker in smallprimes:
		while n % checker == 0:
			factors.append(checker)
			n //= checker
		if checker > n:
			break
	if n != 1:
		factors.append(n)
	if sort:
		factors.sort()
	return factors

def solve(n):
	if n == 1:
		return 1
	som = 1
	if is_prime(n):
		ps = [n]
	else:
		ps = primefactors(n, sort=True)
	for i in range(len(ps)):
		if i == 0:
			som = ps[i] + 1
		else:
			som = ps[i] * som + 1
	return som

def longestSequence(a):
	som = 0
	for m in a:
		som += solve(m)
	return som
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import math
import sys

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

def longestSequence(a):
	t = 0
	for i in a:
		pr = 1
		tt = 1
		s = prime_factors(i)
		for j in range(1, len(s) + 1):
			pr = pr * s[len(s) - j]
			tt += pr
		t += tt
	return t
k = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


n = int(input())
A = map(int, input().split())

def genPrime(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = genPrime(1000000)

def solve(a):
	factors = []
	for p in primes:
		while a % p == 0:
			factors.append(p)
			a = a // p
	if a > 1:
		factors.append(a)
	factors.sort(reverse=True)
	s = 1
	total = 1
	for p in factors:
		s *= p
		total += s
	return total
print(sum((solve(a) for a in A)))


from math import sqrt, ceil

def func(n):
	if n == 0 or n == 1:
		return 0
	if n % 2 == 0:
		return n + func(n // 2)
	else:
		temp = ceil(sqrt(n))
		for i in range(3, temp + 2, 2):
			if n % i == 0:
				return n + func(n // i)
		return n
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	ans += func(a[i]) + 1
print(ans)


import sys
import sys

def pr(n):
	(p, s) = ([], [True] * (n + 1))
	for i in range(2, n + 1):
		if s[i]:
			p.append(i)
			for j in range(i * i, n + 1, i):
				s[j] = False
	return p
values = pr(1000000)
n = int(input())
a = list(map(int, input().split()))
sum = 0
for k in a:
	v = 0
	sum += k
	try:
		while k != 1:
			while k % values[v] == 0:
				k //= values[v]
				sum += k
			v += 1
	except:
		sum += 1
print(sum)


import math

def longestSequence(a):
	smallPrimes = getPrimes(math.ceil(math.sqrt(max(a))))
	print
	result = 0
	for num in a:
		result += getMoves(num, smallPrimes)
	return result

def getPrimes(num):
	listPrimes = []
	isPrime = [True for i in range(num + 1)]
	for i in range(2, num + 1):
		if isPrime[i] == True:
			listPrimes.append(i)
			for j in range(2 * i, num + 1, i):
				isPrime[j] = False
	return listPrimes

def getMoves(num, smallPrimes):
	factors = getFactors(num, smallPrimes)
	moves = 1
	for factor in factors:
		moves = moves * factor + 1
	return moves

def getFactors(num, smallPrimes):
	factors = []
	for i in smallPrimes:
		while num % i == 0:
			factors.append(i)
			num //= i
		if num == 1:
			break
	if num > 1:
		factors.append(num)
	return factors
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import math
import sys

def primes_method5(n):
	if n == 2:
		return [2]
	elif n < 2:
		return []
	s1 = list(range(3, n + 1, 2))
	mroot = n ** 0.5
	half = (n + 1) // 2 - 1
	i = 0
	m = 3
	while m <= mroot:
		if s1[i]:
			j = (m * m - 3) // 2
			s1[j] = 0
			while j < half:
				s1[j] = 0
				j += m
		i = i + 1
		m = 2 * i + 3
	return [2] + [x for x in s1 if x]
l = primes_method5(1000000)

def longestSequence(a):
	li = a
	temp = 0
	s = 0
	flag = 0
	for i in range(len(li)):
		if li[i] == 1:
			flag = 1
			s += 1
		else:
			while li[i] > 1:
				flag = 0
				for j in l:
					if li[i] % j == 0:
						if li[i] == j:
							s += li[i] + 1
							flag = 1
							break
						else:
							s += li[i]
							flag = 1
							break
				if flag == 1:
					li[i] = li[i] // j
				else:
					break
		if flag == 0:
			s += li[i] + 1
	return s
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def maxprimeFactor(n):
	if isprime(n):
		return n
	for x in range(2, int(n ** 0.5 + 1)):
		if not n % x:
			return int(maxprimeFactor(n / x))

def isprime(n):
	for x in range(2, int(n ** 0.5 + 1)):
		if not n % x:
			return False
	return True

def longestSequence(a):
	res = 0
	for i in range(len(a)):
		if a[i] == 1:
			res += 1
		elif a[i] == maxprimeFactor(a[i]):
			res += a[i] + 1
		else:
			res += 1
			j = 1
			while a[i] != maxprimeFactor(a[i]):
				j *= maxprimeFactor(a[i])
				a[i] /= maxprimeFactor(a[i])
				if a[i] != maxprimeFactor(a[i]):
					res += j
			res += j * (a[i] + 1)
	return int(res)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def find_lpf(n):
	las = 0
	while n % 2 == 0 and n != 0:
		n = n // 2
		las = 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0 and n != 0:
			n = n // i
			las = i
	if n > 2:
		las = n
	return las

def find_all(n, lpf):
	if n not in lpf:
		lpf[n] = find_lpf(n)
		find_all(n // lpf[n], lpf)
	pass
n = int(input().strip())
arr = [int(i) for i in input().strip().split(' ')]
lpf = {1: 1}
for i in arr:
	find_all(i, lpf)
ans = 0
for i in arr:
	(temp, su) = (1, 1)
	while i != 1:
		temp *= lpf[i]
		i //= lpf[i]
		su += temp
	ans += su
print(ans)


import sys
import math

def primeFactors(n):
	sum = n
	while n % 2 == 0:
		n = n / 2
		sum += n
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			n = n / i
			sum += n
	if n > 2:
		sum += n % 2
	return int(sum)

def longestSequence(a):
	n = len(a)
	sum = 0
	for i in range(n):
		num = a[i]
		k = primeFactors(num)
		sum += k
	return int(sum)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

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

def largest_prime_factor(n):
	i = 2
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
	return n

def longestSequence(a):
	res = 0
	for i in a:
		if is_prime(i):
			res += 1 + i
		else:
			temp = i
			prod = 1
			no = 1
			while temp != 1:
				res += no * prod
				prod *= no
				no = largest_prime_factor(temp)
				temp = temp // no
			res += i
	return res
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

def isPrime(num):
	for i in range(3, int(math.sqrt(num) + 1), 2):
		if num % i == 0:
			return False
	return True

def returnDivisor(number):
	for i in range(3, int(math.sqrt(number) + 1)):
		if number % i == 0:
			return i

def longestSequence(a):
	moves = 0
	for i in range(len(a)):
		current_length = a[i]
		while current_length:
			if current_length == 1:
				moves += 1
				current_length = 0
			elif current_length % 2 == 0:
				moves += current_length
				current_length = current_length / 2
			elif isPrime(current_length):
				moves += current_length + 1
				current_length = 0
			else:
				moves += current_length
				divisor = returnDivisor(current_length)
				current_length = current_length / divisor
	return moves
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(int(result))


import sys

def nprimes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = nprimes(10 ** 6 + 1)

def longestSequence(a):
	result = 0
	for ai in a:
		factors = []
		for p in primes:
			if ai == 1:
				break
			while ai % p == 0:
				factors.append(p)
				ai = ai // p
		if ai > 1:
			factors.append(ai)
		acc = 1
		res = 1
		while factors:
			n = factors.pop()
			res = res + n * acc
			acc *= n
		result += res
	return result
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import itertools

def erat2():
	D = {}
	yield 2
	for q in itertools.islice(itertools.count(3), 0, None, 2):
		p = D.pop(q, None)
		if p is None:
			D[q * q] = q
			yield q
		else:
			x = p + q
			while x in D or not x & 1:
				x += p
			D[x] = p

def get_primes_erat(n):
	return list(itertools.takewhile(lambda p: p < n, erat2()))

def factors(n, primes):
	factors = []
	rem = n
	for factor in primes:
		while rem % factor == 0:
			rem = rem // factor
			factors.append(factor)
		if rem == 1:
			break
	if rem > 1:
		factors.append(rem)
	return sorted(factors, reverse=True)

def cuts(factors):
	if len(factors) == 0:
		return 0
	if len(factors) == 1:
		return factors[0]
	return factors[0] * (1 + cuts(factors[1:]))

def longestSequence(a):
	val = 0
	primes = get_primes_erat(int(max(a) ** 0.5) + 2)
	for u in a:
		val += cuts(factors(u, primes)) + 1
	return val
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
from math import sqrt

def longestSequence(a):
	most = sum(a)
	for element in a:
		if element == 1:
			pass
		elif isprime(element):
			most += 1
		else:
			most += moves(element)
	return most

def moves(a, val=0):
	if isprime(a):
		return int(val + 1)
	for i in range(2, int(sqrt(a)) + 1):
		if a % i == 0:
			return moves(a / i, val + a / i)

def isprime(n):
	if n <= 1:
		return False
	elif n <= 3:
		return True
	elif 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 += 6
	return True
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys, functools
from math import sqrt

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

def isprime(a):
	if a == 2 or a == 3:
		return True
	if a < 2 or a % 2 == 0:
		return False
	if a < 9:
		return True
	if a % 3 == 0:
		return False
	(r, f) = (int(a ** 0.5), 5)
	while f <= r:
		if a % f == 0:
			return False
		if a % (f + 2) == 0:
			return False
		f += 6
	return True

def longest_for_number(n):
	f = prime_factors(n)
	moves = 1
	product = 1
	for i in reversed(f):
		product *= i
		moves += product
	return moves

def longestSequence(a):
	res = 0
	for i in a:
		if isprime(i):
			res += i + 1
		else:
			res += longest_for_number(i)
	return res
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def seq(x):
	factors = []
	while x != 1:
		if x % 2 == 0:
			factor = 2
		else:
			for i in range(3, x + 1, 2):
				if i * i > x:
					factor = x
					break
				if x % i == 0:
					factor = i
					break
		x //= factor
		factors.append(factor)
	factors.sort(reverse=True)
	moves = 0
	pieces = 1
	for f in factors:
		moves += pieces
		pieces *= f
	moves += pieces
	return moves

def longestSequence(a):
	return sum(map(seq, a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def longestSequence(a):
	add = 0
	for i in a:
		c = i
		f = 0
		while i % 2 == 0:
			c += i / 2
			if i / 2 == 1:
				f = 1
			i = i / 2
		for j in range(3, int(pow(i, 1 / 2)) + 1, 2):
			while i % j == 0:
				c += i / j
				if i / j == 1:
					f = 1
				i = i / j
		if f == 0:
			c += 1
		if c == 2:
			c = 1
		add += c
	return add
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(int(result))


import sys
import math

def longestSequence(a):
	result = 0
	for i in a:
		part = i
		while i % 2 == 0:
			i = i // 2
			part = part + i
		for j in range(3, int(math.sqrt(i)) + 1, 2):
			while i % j == 0:
				i = i // j
				part = part + i
		if i > 2:
			part = part + 1
		result = result + part
	return result
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def moves(m):
	result = m
	while m % 2 == 0:
		m = m // 2
		result += m
	while m % 3 == 0:
		m = m // 3
		result += m
	i = 1
	while 36 * i * i <= m + 1:
		k = 6 * i - 1
		while m % k == 0:
			m = m // k
			result += m
		k = 6 * i + 1
		while m % k == 0:
			m = m // k
			result += m
		i += 1
	if m > 2:
		result += 1
	return result

def longestSequence(a):
	sums = 0
	for a_i in a:
		sums += moves(a_i)
	return sums
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


__author__ = 'Tola'
import sys

def longestSequence(A):
	prime = [2] * 1000001
	prime_list = [2]
	for i in range(3, 1000001, 2):
		if prime[i] == 2:
			prime[i] = i
			j = i
			while j * i < 1000001:
				if prime[i * j] == 2:
					prime[i * j] = i
				j += 2
			prime_list.append(i)
	large_sum = 0
	for a in A:
		if a == 1:
			large_sum += 1
			continue
		sum_instant = a
		if a % 2 == 0:
			p = 2
		elif 2 <= a < 1000000:
			p = prime[a]
		else:
			for p_i in prime_list:
				if a % p_i == 0:
					p = p_i
					break
			else:
				p = a
		while p <= a:
			sum_instant += a // p
			if p == a:
				break
			for q in prime_list:
				temp_p = p * q
				if a % temp_p == 0:
					p = temp_p
					break
			else:
				p = a
		large_sum += sum_instant
	return large_sum
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import math
import sys

def min_divider(x):
	for i in range(2, int(math.sqrt(x)) + 1):
		if not x % i:
			return i
			break
	else:
		return x

def longestSequence(a):
	sum = 0
	for el in a:
		sum += el
		if el != 1:
			while True:
				el = el // min_divider(el)
				sum += el
				if el == 1:
					break
	return sum
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def longestSequence(a):

	def smallestDivisor(n):
		if n % 2 == 0:
			return 2.0
		elif n == 3:
			return 3.0
		else:
			squareRootOfn = int(n ** (1 / 2.0))
			for i in range(3, squareRootOfn + 2, 2):
				if n % i == 0:
					return i
				elif i >= squareRootOfn:
					return n
	cumsum = 0
	for num in a:
		cumsum += num
		while num > 1:
			num = num / smallestDivisor(num)
			cumsum += num
	return int(cumsum)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

def is_prime(n):
	if n % 2 == 0 and n > 2:
		return False
	if n == 2:
		return True
	for i in range(3, int(math.sqrt(n)) + 2, 2):
		if n % i == 0:
			return False
	return True

def least_prime_factor(n):
	if n % 2 == 0:
		return 2
	for i in range(3, int(math.sqrt(n)) + 2, 2):
		if n % i == 0:
			if is_prime(i):
				return i

def longestSequence(a):
	steps = 0
	for i in a:
		if i == 1:
			steps += 1
		else:
			ni = i
			while ni != 1:
				lpf = least_prime_factor(ni)
				if lpf is None:
					lpf = ni
				ni = ni // lpf
				steps += ni
			steps += i
	return steps
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import math
import sys
from collections import defaultdict

def primes_upto(n):
	if n <= 1:
		return []
	A = defaultdict(lambda : True)
	A[0] = False
	A[1] = False
	root_n = int(math.sqrt(n))
	for i in range(2, root_n + 1):
		i_squared = i * i
		if A[i]:
			for j in range(i_squared, n + 1, i):
				A[j] = False
	return (i for i in range(n + 1) if A[i])
primes = list(primes_upto(10 ** 6))

def prime_factors(n):
	if n < 2:
		return []
	i = 0
	while i < len(primes):
		p = primes[i]
		if n == p:
			break
		if n % p == 0:
			yield p
			n //= p
		else:
			i += 1
	yield n

def optimal_breaks(n):
	total = 1
	for f in prime_factors(n):
		total = total * f + 1
	return total

def longest_sequence(a):
	return sum((optimal_breaks(b) for b in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longest_sequence(a)
print(result)


import sys
from functools import reduce

def primesBelow(bound):
	map = [True for i in range(bound + 1)]
	r = []
	p = 2
	while p <= bound:
		r += [p]
		for i in range(p, bound + 1, p):
			map[i] = False
		while p <= bound and (not map[p]):
			p += 1
	return r
primes = primesBelow(10 ** 6)

def longestSequenceSingle(n):
	if 1 == n:
		return 1
	factors = []
	for p in primes:
		if n % p == 0:
			while n % p == 0:
				factors.append(p)
				n //= p
	if 1 != n:
		factors.append(n)
	return reduce(lambda e, r: 1 + e * r, factors, 1)

def longestSequence(a):
	return sum((longestSequenceSingle(n) for n in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def factors(n):
	while n % 2 == 0:
		n //= 2
		yield 2
	j = 3
	while n > 1:
		for i in range(j, int((n + 0.05) ** 0.5) + 1, 2):
			if n % i == 0:
				n //= i
				j = i
				yield i
				break
		else:
			if n > 1:
				yield n
				break

def find(n):
	retVal = 1
	for f in factors(n):
		retVal *= f
		retVal += 1
	return retVal

def longestSequence(a):
	return sum((find(i) for i in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
from math import sqrt

def longestSequence(a):
	max_stick = max(a)
	primes = [2, 3]
	result = 0
	for i in range(5, int(sqrt(max_stick)) + 1, 2):
		isPrime = True
		for j in primes:
			if i % j == 0:
				isPrime = False
				break
			if j > sqrt(i):
				break
		if isPrime:
			primes.append(i)
	served = {}
	for stick in a:
		if stick in served:
			result += served[stick]
		else:
			tmp = stick
			res = 0
			for prime in primes:
				while tmp % prime == 0:
					tmp = tmp // prime
					res += tmp
				if prime > tmp:
					break
			res += stick
			if tmp != 1:
				res += 1
			result += res
			served[stick] = res
	return result
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
memoization = {}
primeMemoization = {}
primes = []
primeBools = [True for i in range(1000000)]
primeBools[0] = False
primeBools[1] = False
for i in range(1000000):
	if primeBools[i] != False:
		for j in range(i ** 2, 1000000, i):
			primeBools[j] = False
for i in range(2, 1000000):
	if primeBools[i] == True:
		primes.append(i)
		primeMemoization[i] = i + 1
primeMemoization[1] = 1

def longestSequence(a):
	totalMoves = 0
	for num in a:
		totalMoves += calcMoves(num)
	return totalMoves

def calcMoves(num):
	curMoves = num
	curNum = num
	while curNum not in primeMemoization:
		for prime in primes:
			if curNum % prime == 0:
				curMoves += curNum // prime
				curNum = curNum // prime
				break
		else:
			primeMemoization[curNum] = curNum + 1
	if curMoves > 1:
		curMoves += 1
	return curMoves
result = longestSequence(a)
print(result)


import sys
from math import sqrt

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

def getPrimeComponent(n):
	result = n
	cur = 2
	while n != 1 and n % 2 == 0:
		n = int(n / 2)
		result += n
	cur += 1
	check = False
	while n != 1:
		n1 = n
		while n % cur == 0:
			n = int(n / cur)
			result += n
		cur += 2
		if n1 != n:
			check = False
		if not check and n != 1 and isPrime(int(n)):
			result += int(1)
			break
		else:
			check = True
	return result

def longestSequence(a):
	final = 0
	for n in a:
		final += getPrimeComponent(n)
	return final
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
prime_cache = {}

def prime_factors(n):
	loop = 0
	factors = []
	d = 2
	while n > 1:
		loop += 1
		while n % d == 0:
			factors.append(d)
			n /= d
		d = d + 1
		if d * d > n:
			if n > 1:
				factors.append(n)
			break
		if loop > 100000:
			return [n]
	return factors

def largest_prime_factor(n):
	if n in prime_cache:
		return prime_cache[n]
	pfs = prime_factors(n)
	m = max(pfs)
	prime_cache[n] = m
	return m

def moves(a):
	found = []
	candidates = [(a, [])]
	while True:
		new_candidates = []
		for candidate in candidates:
			if candidate[0] == 1:
				hist = list(candidate[1])
				hist.append(candidate[0])
				found.append(hist)
			else:
				max_prime = largest_prime_factor(candidate[0])
				hist2 = list(candidate[1])
				hist2.append(candidate[0])
				new_candidate = (candidate[0] // max_prime, hist2)
				new_candidates.append(new_candidate)
		if len(new_candidates) == 0:
			break
		candidates = new_candidates
	for c in found:
		splits = []
		for x in range(0, len(c) - 1):
			splits.append(c[x] // c[x + 1])
		summ = 1
		mul = 1
		for s in splits:
			mul *= s
			summ += mul
	return int(summ)

def longestSequence(a):
	return sum(map(moves, a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math as m

def factor(n, prms):
	for i in prms:
		if n % i == 0:
			return (n // i, i)
	return (n, 1)

def factors(n, prms):
	resul = []
	while n > 1:
		(n, newf) = factor(n, prms)
		if newf == 1:
			resul += [n]
			break
		resul += [newf]
	resul.sort()
	return resul

def nume(x, prms):
	(total, nivel) = (0, 1)
	facts = factors(x, prms)
	for x in reversed(facts):
		nivel = nivel * x
		total = total + nivel
	return 1 + total

def genprimes(limit):
	D = {}
	q = 2
	while q <= limit:
		if q not in D:
			yield q
			D[q * q] = [q]
		else:
			for p in D[q]:
				D.setdefault(p + q, []).append(p)
			del D[q]
		q += 1

def longestSequence(a):
	p = genprimes(1000000)
	prms = [i for i in p]
	res = 0
	while len(a) > 0:
		res += nume(a.pop(), prms)
	return res
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [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]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 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, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [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]
	for k in range(1, n // 210):
		for j in [1, 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, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 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, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def is_miller_rabin(x, num_tests=3):
	k = x - 1
	e = 0
	while k % 2 == 0:
		e += 1
		k //= 2
	tests = [False for _ in range(0, num_tests)]
	A = [2, 3, 5]
	for j in range(3, num_tests):
		A.append(random.randint(7, x - 1))
	if x < 2047:
		num_tests = 1
	elif x < 1373653:
		num_tests = 2
	elif x < 25326001:
		num_tests = 3
	for i in range(0, num_tests):
		ak = pow_mod(A[i], k, x)
		if ak == 1:
			tests[i] = True
		else:
			for j in range(0, e):
				if ak == x - 1:
					tests[i] = True
				ak = ak * ak % x
	for i in range(0, num_tests):
		if not tests[i]:
			return False
	return True

def factor(n, PL):
	sqrt = int(pow(n, 0.5)) + 1
	factor_list = []
	if not PL:
		PL = prime_list(sqrt)
	for p in PL:
		if n % p == 0:
			elet = [p, 0]
			while not n % p:
				n //= p
				elet[1] += 1
			factor_list.append(elet)
	if n != 1:
		if is_miller_rabin(n):
			factor_list.append([n, 1])
	return factor_list

def longestSequence(a):
	PL = prime_list(200000)
	factors_list = [factor(a_i, PL) for a_i in a]
	sequence_list = []
	for i in range(0, len(factors_list)):
		total = 1
		current = 1
		for j in range(0, len(factors_list[i])):
			power_k = len(factors_list[i])
			for k in range(0, factors_list[i][power_k - 1 - j][1]):
				current *= factors_list[i][power_k - 1 - j][0]
				total += current
		sequence_list.append(total)
	return sum(sequence_list)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import functools
fs = {}

def factor(n, startFrom=2):
	n2 = n
	if n not in fs:
		if n <= 1:
			return []
		d = startFrom
		factors = []
		while n >= d * d:
			if n % d == 0:
				factors.append(d)
				n = n / d
			else:
				d += 1 + d % 2
		factors.append(n)
		fs[n2] = factors
	return fs[n2]

def listPrimes(n):
	if n <= 2:
		return []
	sieve = [True] * n
	primes = [2]
	i = 3
	while i < n:
		if sieve[i]:
			primes.append(i)
			for mult in range(i * i, n, i):
				sieve[mult] = False
		i += 2
	return primes

def factorGivenPrimes(n, primes):
	p = 0
	factors = []
	for p in primes:
		while n % p == 0:
			n /= p
			factors.append(p)
		if n < p * p:
			if n > 1:
				factors.append(n)
			return factors
	return factors + factor(n, p + 2)
ps = listPrimes(10 ** 6)

def ls(a):
	if a == 1:
		return 1
	facs = factorGivenPrimes(a, ps)
	if len(facs) == 0:
		return a + 1
	x = 1
	for f in facs:
		while a % f == 0:
			a /= f
			x *= f
			x += 1
	return int(x)

def longestSequence(a):
	return sum([ls(x) for x in a])
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import bisect
import math
import sys

def longestSequence(a):
	limit = 10 ** 6
	primes = []
	isprime = [True] * limit
	isprime[0] = isprime[1] = False
	for i in range(2, len(isprime)):
		if isprime[i]:
			primes.append(i)
			for j in range(i * i, limit, i):
				isprime[j] = False
	moves = 0
	for e in a:
		move = e
		search = bisect.bisect(primes, int(math.sqrt(e)))
		search = min(search, len(primes) - 1)
		divisors = []
		for i in range(0, search + 1):
			while e % primes[i] == 0:
				divisors.append(primes[i])
				e //= primes[i]
			if e == 1:
				break
		if e > 1:
			divisors.append(e)
		temp = 1
		for i in range(len(divisors) - 1, -1, -1):
			move += temp
			temp *= divisors[i]
		moves += move
	return moves
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math

def primeFactors(n):
	maxSum = 0
	while n % 2 == 0:
		n = n / 2
		maxSum += n
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			n = n / i
			maxSum += n
	if n > 2:
		maxSum += 1
	return maxSum

def longestSequence(a):
	maxSum = 0
	for aNum in a:
		if aNum == 1:
			maxSum += 1
			continue
		b = aNum + primeFactors(aNum)
		maxSum += b
	return int(maxSum)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math
import random

def prime(n, k):
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	(r, s) = (0, n - 1)
	while s % 2 == 0:
		r += 1
		s //= 2
	for _ in range(k):
		a = random.randint(2, n - 1)
		x = pow(a, s, n)
		if x == 1 or x == n - 1:
			continue
		for _ in range(r - 1):
			x = pow(x, 2, n)
			if x == n - 1:
				break
		else:
			return False
	return True
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
max_sum = 0
for num in a:
	sum = num
	if num == 1:
		max_sum += sum
	else:
		while 1:
			if num % 2 == 0:
				num = num // 2
				sum += num
			elif prime(num, 10) and num != 1:
				sum += 1
				break
			else:
				for j in range(2, num + 1):
					if num % j == 0 and j % 2 != 0:
						num = num // j
						sum += num
						break
			if num == 1:
				break
		max_sum += sum
print(max_sum)


import sys
import math

def prime_factorize(n):
	factors = []
	number = abs(n)
	factor = 2
	while number > 1:
		factor = get_next_prime_factor(number, factor)
		factors.append(factor)
		number /= factor
	if n < -1:
		factors[0] = -factors[0]
	return factors

def get_next_prime_factor(n, f):
	if n % 2 == 0:
		return 2
	for x in range(max(f, 3), int(math.sqrt(n) + 1), 2):
		if n % x == 0:
			return x
	return n

def longestSequence(a):
	totalsum = 0
	for elem in a:
		pf = prime_factorize(elem)
		thistotal = elem
		if elem != 1:
			thistotal += 1
		carry = 1
		for i in sorted(pf, reverse=True)[:-1]:
			carry *= i
			thistotal += carry
		totalsum += thistotal
	return int(totalsum)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


mem = dict()

def get_primes_to(n):
	(D, q) = ({}, 2)
	while q <= n:
		if q not in D:
			yield q
			D[q * q] = [q]
		else:
			for p in D[q]:
				D.setdefault(p + q, []).append(p)
			del D[q]
		q += 1

def solve(n, pp):
	if 1 == n:
		return 1
	if n in mem:
		return mem[n]
	i = 0
	while i < len(pp):
		if not n % pp[i]:
			mem[n] = n + solve(n // pp[i], pp)
			break
		else:
			i += 1
	else:
		mem[n] = n + 1
	return mem[n]
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
pp = list(get_primes_to(int(max(a) ** 0.5)))
print(sum((solve(e, pp) for e in a)))


import sys
import math

def longestSequence(a):
	y = 0
	for x in a:
		sums = x
		while x % 2 == 0:
			x = x // 2
			sums = sums + x
		for i in range(3, int(math.sqrt(x)) + 1, 2):
			while x % i == 0:
				x = x // i
				sums = sums + x
		if x > 2:
			sums = sums + 1
		y = y + sums
	print(y)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
longestSequence(a)


import sys
import math

def listPrimeFact(num):
	facts = []
	while num % 2 == 0:
		facts.append(2)
		num = num // 2
	for i in range(3, int(math.sqrt(num)) + 1, 2):
		while num % i == 0:
			facts.append(i)
			num = num // i
	if num > 2:
		facts.append(num)
	return facts

def findSeq(num):
	fact = listPrimeFact(num)
	fact.sort(reverse=True)
	sum = 0
	mult = 1
	for i in fact:
		mult = mult * i
		sum = sum + mult
	return sum + 1

def longestSequence(a):
	sum = 0
	for i in a:
		sum += findSeq(i)
	return sum
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import functools

@functools.lru_cache(maxsize=None)
def factor(n):
	assert n != 1
	if n == 2 or n == 3:
		return (n,)
	if n % 2 == 0:
		b = factor(n // 2)
		return b if b[0] == 2 else (2,) + b
	if n % 3 == 0:
		b = factor(n // 3)
		return b if 3 in b[:2] else (3,) + b
	p = 5
	while n != 1 and p <= n ** 0.5:
		if n % p == 0:
			b = factor(n // p)
			return b if p in b else (p,) + b
		p += 2
		if n % p == 0:
			b = factor(n // p)
			return b if p in b else (p,) + b
		p += 4
	if n != 1:
		return (n,)

@functools.lru_cache(maxsize=None)
def f(n):
	if n == 1:
		return 0
	factors = factor(n)
	if factors[0] == n:
		return 1
	return 1 + max((p * f(n // p) for p in factors))

def longestSequence(a):
	return sum((n + f(n) for n in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def longestSequence(a):
	import math

	def make_primes(num):
		if num < 2:
			return []
		num_sqrt = math.sqrt(num)
		candidates = [i for i in range(2, num + 1)]
		primes = []
		while True:
			target = candidates.pop(0)
			primes.append(target)
			candidates = [i for i in candidates if i % target != 0]
			if not candidates:
				break
			if candidates[0] > num_sqrt:
				primes.extend(candidates)
				break
		return primes

	def largest_divisor(num, primes):
		for prime in primes:
			if num % prime == 0:
				return num // prime
		return 1

	def longest(n):
		if n < 2:
			return n
		array = [n]
		primes = make_primes(100000)
		while True:
			target = largest_divisor(n, primes)
			array.append(target)
			if target == 1:
				break
			n = target
		return sum(array)
	return sum([longest(i) for i in a])
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys

def longestSequence(a):
	totalNumber = 0
	for x in range(len(a)):
		currentStick = a[x]
		totalNumber += currentStick
		i = 2
		while currentStick % i == 0:
			currentStick /= i
			totalNumber += currentStick
		i = 3
		while i * i <= currentStick:
			while currentStick % i == 0:
				currentStick /= i
				totalNumber += currentStick
			i += 2
		if currentStick > 1:
			totalNumber += 1
	return int(totalNumber)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def sieve_generate(n):
	n = int(n ** 0.5) + 1
	num_list = [1] * n
	num_list[0] = num_list[1] = 0
	for i in range(3, n, 2):
		for j in range(2 * i, n, i):
			num_list[j] = 0
	s = [2]
	for k in range(3, n, 2):
		if num_list[k]:
			s.append(k)
	return s

def longest_sequence(a):
	sieve = sieve_generate(max(a) + 1)
	for i in range(len(a)):
		if a[i] == 1:
			continue
		elif a[i] in sieve:
			a[i] += 1
		else:
			f = []
			t = a[i]
			for j in sieve:
				if j > a[i]:
					break
				while t % j == 0:
					f.append(j)
					t /= j
			if t > 1:
				f.append(int(t))
			m = 1
			s = 1
			for j in reversed(f):
				m *= j
				s += m
			a[i] = s
	return sum(a)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longest_sequence(a)
print(result)


import sys
import math

def longestSequence(a):
	moves = 0
	for x in a:
		moves += break_chocolate(x, 0)
	return moves

def break_chocolate(number, moves):
	if number == 1:
		return moves + number
	if number % 2 == 0:
		for x in range(2, int(math.sqrt(number) + 1)):
			if number % x == 0:
				moves += number
				return break_chocolate(int(number / x), moves)
	else:
		for x in range(3, int(math.sqrt(number) + 1), 2):
			if number % x == 0:
				moves += number
				return break_chocolate(int(number / x), moves)
	moves += number
	return break_chocolate(int(number / number), moves)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import math
from collections import defaultdict

def f(n):
	d = defaultdict(int)
	n1 = n
	while n % 2 == 0:
		d[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n = n // i
	if n > 2:
		d[n] += 1
	m = 0
	for k in sorted(d.keys()):
		while d[k] > 0:
			m += n1
			d[k] -= 1
			n1 = n1 // k
	return m

def longestSequence(a):
	s = 0
	for c in a:
		s += f(c) + 1
	return s
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
MAX = 1000000

def get_prime_list(max_number):
	result = []
	prime_flag = [True for i in range(max_number + 1)]
	for i in range(2, max_number + 1):
		if prime_flag[i] == True:
			result.append(i)
			j = i + i
			while j <= max_number:
				prime_flag[j] = False
				j += i
	return result

def find_max_prime(num, primes):
	for p_index in range(len(primes) - 1, -1, -1):
		prime = primes[p_index]
		while num % prime == 0:
			num = int(num / prime)
	return num

def longestSequence(a):
	result = 0
	primes = get_prime_list(MAX)
	for num in a:
		stick = 1
		move = 1
		max_prime = find_max_prime(num, primes)
		if max_prime != 1:
			stick = max_prime
			move += max_prime
			num = int(num / max_prime)
		for p_index in range(len(primes) - 1, -1, -1):
			prime = primes[p_index]
			while num % prime == 0:
				stick *= prime
				move += stick
				num = int(num / prime)
		if num != 1:
			move += num
		result += move
	return result
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


import sys
import itertools as it
from operator import mul
from functools import reduce
from collections import defaultdict

class Sequencer:

	def __init__(self, maxA):
		r = int(maxA ** 0.5)
		while (r + 1) * (r + 1) <= maxA:
			r += 1
		self.primes = self.makePrimes(r)
		self.cache = {}
		self.cache[1] = 1

	def __call__(self, n):
		try:
			return self.cache[n]
		except KeyError:
			pass
		divisors = self.findProperDivisors(n)
		ans = max([n // d * self(d) + 1 for d in divisors])
		self.cache[n] = ans
		return ans

	def makePrimes(self, n):
		isPrime = [True] * (n + 1)
		isPrime[0] = isPrime[1] = False
		for p in range(2, n + 1):
			if p * p > n:
				break
			if not isPrime[p]:
				continue
			for x in range(p * p, n + 1, p):
				isPrime[x] = False
		return [x for x in range(2, n + 1) if isPrime[x]]

	def findProperDivisors(self, n):
		primeFactor = defaultdict(int)
		m = n
		for p in self.primes:
			if p * p > m:
				break
			while m % p == 0:
				m //= p
				primeFactor[p] += 1
		if not m == 1:
			primeFactor[m] += 1
		primePowers = tuple(([p ** x for x in range(primeFactor[p] + 1)] for p in primeFactor.keys()))
		divs = [reduce(lambda x, y: x * y, q, 1) for q in it.product(*primePowers)]
		divs.sort()
		return divs[:-1]

def longestSequence(a):
	sequencer = Sequencer(max(a))
	return sum([sequencer(x) for x in a])
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


def factor_trial_division(x):
	if x <= 1:
		return []
	f = []
	e = 0
	while x % 2 == 0:
		x //= 2
		e += 1
	if e > 0:
		f.append([2, e])
	p = 3
	while p * p <= x:
		e = 0
		while x % p == 0:
			x //= p
			e += 1
		if e > 0:
			f.append([p, e])
		p += 2
	if x > 1:
		f.append([x, 1])
	return sorted(f)

def longest_sequence_single_stick(stick, factors=[]):
	if stick <= 3:
		return [0, 1, 3, 4][stick]
	factors = factor_trial_division(stick)
	lpf = factors[-1][0]
	factors[-1][1] -= 1
	if factors[-1][1] == 0:
		factors = factors[:-1]
	num_moves = 1 + lpf * longest_sequence_single_stick(stick // lpf, factors)
	return num_moves

def longest_sequence_multiple_sticks(sticks):
	return sum((longest_sequence_single_stick(stick) for stick in sticks))
n = int(input().strip())
sticks = list(map(int, input().strip().split(' ')))
result = longest_sequence_multiple_sticks(sticks)
print(result)


def getP(N):
	A = [True for n in range(N + 1)]
	A[0] = False
	A[1] = False
	for n in range(2, int(N ** 0.5) + 1):
		if not A[n]:
			continue
		for d in range(2 * n, N + 1, n):
			A[d] = False
	P = []
	for (i, a) in enumerate(A):
		if a:
			P.append(i)
	return P

def f(a):
	B = []
	i = 0
	while a > 1:
		while a % P[i] == 0:
			B.append(P[i])
			a //= P[i]
		i += 1
		if i > len(P) - 1:
			B.append(a)
			break
	s = 0
	p = 1
	for b in reversed(B):
		s += p
		p *= b
	s += p
	return s
P = getP(10 ** 6)
N = int(input())
A = [int(a) for a in input().split()]
s = 0
for a in A:
	s += f(a)
print(s)


import sys
from time import time

def primes_gen(n):
	sieve = [1] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = 0

def pfs_gen(n, prms):
	for p in prms:
		if p > n:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
	if n > 1:
		yield (n, 1)

def moves(a, prms):
	if a < 2:
		return 1
	(total, parts) = (0, 1)
	for (p, c) in reversed(tuple(pfs_gen(a, prms))):
		for _ in range(c):
			total += parts
			parts *= p
	return total + parts

def solve(aa):
	prms = tuple(primes_gen(int(pow(max(aa), 1 / 2)) + 2))
	print('primes generated: %d max=%d' % (len(prms), prms[-1]), file=sys.stderr)
	sm = 0
	for a in aa:
		m = moves(a, prms)
		sm += m
		print('a=%d m=%d' % (a, m), file=sys.stderr)
	return sm
_ = int(input())
aa = list(map(int, input().split()))
print(solve(aa))


import sys

def factorize(n):
	res = []
	if n % 2 == 0:
		power = 0
		while n % 2 == 0:
			power += 1
			n //= 2
		res.append((2, power))
	i = 3
	while i * i <= n:
		if n % i == 0:
			power = 0
			while n % i == 0:
				power += 1
				n //= i
			res.append((i, power))
		i += 2
	if n > 1:
		res.append((n, 1))
	return res

def f(x):
	res = 1
	mul = 1
	for (p, power) in factorize(x)[::-1]:
		res += mul * ((p ** (power + 1) - 1) // (p - 1) - 1)
		mul *= p ** power
	return res

def longestSequence(a):
	return sum((f(x) for x in a))
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
result = longestSequence(a)
print(result)


from functools import lru_cache

def get_primes(n):
	return [i for (i, x) in enumerate(primes_raw(n)) if x]

def primes_raw(n):
	(i, s) = (2, [True for x in range(0, n + 1)])
	while i * i <= n:
		if s[i]:
			for c in range(2 * i, n + 1, i):
				s[c] = False
		i += 1
	return [False, False] + s[2:]

@lru_cache(None)
def factors(n):
	fs = []
	for f in primes:
		if n % f == 0:
			fs = [f] + factors(n // f)
			break
		if f > n:
			break
	else:
		fs = [n]
	return fs

def solve(n):
	fs = factors(n)
	steps = 0
	pieces = 1
	for f in fs[::-1]:
		steps += pieces
		pieces *= f
	return steps + n
primes = get_primes(10 ** 6 + 1)
t = int(input())
ns = list(map(int, input().split()))
print(sum(map(solve, ns)))