Given an integer $n$.

Consider all pairs of integer arrays $a$ and $p$ of the same length such that $n = \prod a_i^{p_i}$ (i.e. $a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$) ($a_i>1;p_i>0$) and $a_i$ is the product of some (possibly one) distinct prime numbers.

For example, for $n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1$ the array pair $a = [2, 7]$, $p = [2, 1]$ is correct, but the pair of arrays $a = [4, 7]$, $p = [1, 1]$ is not, because $4=2^2$ is a product of non-distinct prime numbers.

Your task is to find the maximum value of $\sum a_i \cdot p_i$ (i.e. $a_1\cdot p_1 + a_2\cdot p_2 + \ldots$) over all possible pairs of arrays $a$ and $p$. Note that you do not need to minimize or maximize the length of the arrays.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Each test case contains only one integer $n$ ($2 \le n \le 10^9$).


-----Output-----

For each test case, print the maximum value of $\sum a_i \cdot p_i$.


-----Examples-----

Input
7
100
10
864
130056192
1000000000
2
999999018
Output
20
10
22
118
90
2
333333009


-----Note-----

In the first test case, $100 = 10^2$ so that $a = [10]$, $p = [2]$ when $\sum a_i \cdot p_i$ hits the maximum value $10\cdot 2 = 20$. Also, $a = [100]$, $p = [1]$ does not work since $100$ is not made of distinct prime factors.

In the second test case, we can consider $10$ as $10^1$, so $a = [10]$, $p = [1]$. Notice that when $10 = 2^1\cdot 5^1$, $\sum a_i \cdot p_i = 7$.

Difficulty: EASY
Tags: Number theory

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from typing import List

def get_primes(size: int) -> List[int]:
	is_prime = [True for _ in range(size + 1)]
	primes = []
	for i in range(2, size + 1):
		if is_prime[i]:
			primes.append(i)
			for j in range(i * i, size + 1, i):
				is_prime[j] = False
	return primes
max = 10 ** 9
primes = get_primes(int(max ** 0.5) + 1)

def val(n: int) -> int:
	primes_and_powers = []
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power > 0:
			primes_and_powers.append([p, power])
	if n > 1:
		primes_and_powers.append([n, 1])
	res = 0
	mul = 0
	while mul != 1:
		mul = 1
		for i in range(len(primes_and_powers)):
			if primes_and_powers[i][1] > 0:
				mul *= primes_and_powers[i][0]
				primes_and_powers[i][1] -= 1
		res += mul
	return res - 1
T = int(input())
for _ in range(T):
	n = int(input())
	print(val(n))


def sieve_of_eratosthenes(n):
	primes = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if primes[p]:
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return [p for p in range(2, n + 1) if primes[p]]

def prime_factors(n, primes):
	factors = []
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			factors.append(p)
			n = n // p
	if n > 1:
		factors.append(n)
	return factors
primes = sieve_of_eratosthenes(10 ** 6)
for _ in range(int(input())):
	a = int(input())
	li = prime_factors(a, primes)
	se = set(li)
	se = list(se)
	co = []
	for i in se:
		co.append(li.count(i))
	sm = 0
	zo = max(co)
	fino = []
	while zo > 0:
		pro = 1
		for i in range(len(se)):
			if co[i] > 0:
				pro = pro * se[i]
				co[i] = co[i] - 1
		fino.append(pro)
		zo = zo - 1
	print(int(sum(fino)))


import math

def main():
	_i = int(input())
	for _ in range(_i):
		n = int(input().strip('\r\n'))
		counts = {}
		_n = n
		if _n % 2 == 0:
			counts[2] = 0
			while _n % 2 == 0:
				counts[2] += 1
				_n /= 2
		i = 3
		sqn = int(math.sqrt(_n))
		while _n > 1:
			flag = False
			while _n % i == 0:
				flag = True
				if i in counts:
					counts[i] += 1
				else:
					counts[i] = 1
				_n = _n // i
			if flag:
				sqn = int(math.sqrt(_n))
			if i > sqn:
				counts[int(_n)] = 1
				break
			i += 2
		scnts = sorted(counts.items(), key=lambda x: x[1])
		res = 1
		for val in counts:
			res *= val
		cur_mul = res
		res *= scnts[0][1]
		prev_cnt = scnts[0][1]
		for (val, cnt) in scnts:
			if cnt > prev_cnt:
				res += cur_mul * (cnt - prev_cnt)
				prev_cnt = cnt
			cur_mul = cur_mul // val
		print(res)
main()


from collections import Counter
import sys
input = sys.stdin.readline

def prime(n):
	arr = [True for _ in range(n + 1)]
	m = int(n ** 0.5)
	for i in range(2, m + 1):
		if arr[i] == True:
			for j in range(2 * i, n + 1, i):
				arr[j] = False
	return [i for i in range(2, n + 1) if arr[i] == True]
a = prime(31623)
T = int(input())
for _ in range(T):
	n = int(input())
	m = int(n ** 0.5)
	board = []
	for i in a:
		if n == 1:
			break
		while n % i == 0:
			n //= i
			board.append(i)
	if n != 1:
		board.append(n)
	board = Counter(board)
	sumall = 0
	while 1:
		val = list(board.values())
		if len(val) == 0:
			break
		min_count = min(val)
		g = 1
		key = list(board.keys())
		for i in key:
			board[i] -= min_count
			if board[i] == 0:
				del board[i]
			g *= i
		sumall += g * min_count
	print(sumall)


import sys

def solve():
	n = int(sys.stdin.readline())
	cnt = []
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	if c != 0:
		cnt.append((c, 2))
	for i in range(3, n, 2):
		if i * i > n:
			break
		c = 0
		while n % i == 0:
			n //= i
			c += 1
		if c != 0:
			cnt.append((c, i))
	if n != 1:
		cnt.append((1, n))
	cnt.sort()
	now = 1
	for (_, v) in cnt:
		now *= v
	z = 0
	ans = 0
	for i in range(len(cnt)):
		c = cnt[i][0]
		while z < c:
			z += 1
			ans += now
		now //= cnt[i][1]
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import math
from math import prod
for _ in range(int(input())):
	n = int(input())
	simple_nums = []
	while n % 2 == 0:
		simple_nums.append(2)
		n = n >> 1
	for i in range(3, math.floor(math.sqrt(n)) + 1, 2):
		if i * i > n:
			break
		while not n % i:
			simple_nums.append(i)
			n = n // i
	if n > 1:
		simple_nums.append(n)
	summ = 0
	while simple_nums:
		s = set(simple_nums)
		summ += prod(s)
		for a in s:
			simple_nums.remove(a)
	print(summ)


for _ in range(int(input())):
	n = int(input())
	pf = []
	while n > 0:
		m = n
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				pf.append(i)
				n //= i
				break
		if m == n:
			pf.append(n)
			n = 0
	ans = 0
	i = 0
	while True:
		x = pf[i]
		z = pf[i]
		pf[i] = 0
		if x == 0:
			pass
		else:
			for j in range(len(pf)):
				if pf[j] != z and pf[j] != 0:
					x *= pf[j]
					z = pf[j]
					pf[j] = 0
			ans += x
		for v in pf:
			if v != 0:
				break
		else:
			break
		i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [1 for i in range(0, 30)]
	i = 2
	while i * i <= n:
		j = 0
		while n % i == 0:
			a[j] *= i
			n //= i
			j += 1
		if i == 2:
			i += 1
		else:
			i += 2
	a[0] *= n
	ans = 0
	for i in range(0, 30):
		if a[i] > 1:
			ans += a[i]
	print(ans)


def pfacs(n):
	res = dict()
	for i in range(2, n + 1):
		if i * i > n:
			if n > 1:
				res[n] = 1
			break
		if n % i == 0:
			k = 0
			while n % i == 0:
				k += 1
				n //= i
			res[i] = k
	return res

def solve(n):
	res = 0
	ap = sorted(pfacs(n).items(), key=lambda x: x[1])
	while ap:
		temp = []
		k = ap[0][1]
		s = 1
		for (a, p) in ap:
			s *= a
			if p - k > 0:
				temp.append((a, p - k))
		res += k * s
		ap = temp
	print(res)
t = int(input())
for test in range(t):
	n = int(input())
	solve(n)


def ss(n):
	i = 2
	x = {}
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			if i in x:
				x[i] += 1
			else:
				x[i] = 1
	if n > 1:
		if n in x:
			x[n] += 1
		else:
			x[n] = 1
	t = 0
	for i in x:
		t = max(t, x[i])
	ans = [0 for _ in range(t + 1)]
	for i in x:
		for j in range(x[i]):
			if ans[j] == 0:
				ans[j] = 1
			ans[j] *= i
	return sum(ans)
for _ in range(int(input())):
	n = int(input())
	print(ss(n))


import math

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
for _ in range(int(input())):
	n = int(input())
	l = []
	l = prime_factors(n)
	if len(l) <= 1:
		print(n)
		continue
	count = 1
	ma = 0
	for i in range(len(l) - 1):
		if l[i] == l[i + 1]:
			count += 1
		else:
			ma = max(count, ma)
			count = 1
	ma = max(count, ma)
	l2 = [1] * ma
	j = 0
	for i in range(len(l) - 1):
		l2[j] *= l[i]
		if l[i] == l[i + 1]:
			j += 1
		else:
			j = 0
	if l[-1] == l[-2]:
		l2[j] *= l[-1]
	else:
		l2[0] *= l[-1]
	print(sum(l2))


import math
nb_t = int(input())

def prime_factor(n):
	i = 2
	res = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			res.append(i)
	return res + [n]
for _ in range(nb_t):
	n = int(input())
	pf = prime_factor(n)
	pn = set(pf)
	po = [pf.count(i) for i in pn]
	c = sorted([[n, p] for (n, p) in zip(pn, po)], key=lambda x: x[1])
	nb_po = sum(po)
	res = 0
	while nb_po > 0:
		temp = []
		for i in range(len(po)):
			if c[i][1] > 0:
				temp.append(c[i][0])
				c[i][1] -= 1
				nb_po -= 1
		res += math.prod(temp)
	print(res)


import math
from collections import deque
total = int(input())

def all_factors(p):
	res = []
	for i in range(2, p // 2):
		if i * i > p:
			break
		if p % i == 0:
			count = 0
			while p % i == 0:
				p //= i
				count += 1
			res.append((i, count))
	if p:
		res.append((p, 1))
	return res

def func(i):
	factors = deque(all_factors(i))
	res = 0
	while factors:
		size = len(factors)
		cur = 1
		for _ in range(size):
			(f, count) = factors.popleft()
			cur *= f
			if count > 1:
				factors.append((f, count - 1))
		res += cur
	return res
for i in range(total):
	print(func(int(input())))


import math

def primfacs_dict(n):
	i = 2
	prims_collection = {}
	while i * i <= n:
		while n % i == 0:
			prims_collection[i] = prims_collection.get(i, 0) + 1
			n = n // i
		i = i + 1
	if n > 1:
		prims_collection[n] = prims_collection.get(int(n), 0) + 1
	return prims_collection
t = int(input())
for i in range(t):
	n = int(input())
	prims_collection = primfacs_dict(n)
	res = 0
	rem_res = math.prod(prims_collection.keys())
	rem_l = []
	while prims_collection:
		temp_keys = prims_collection.keys()
		min_temp = min(prims_collection.values())
		rem_res = rem_res // math.prod(rem_l)
		res += rem_res * min_temp
		for k in prims_collection.keys():
			prims_collection[k] -= min_temp
		temp = {}
		rem_l = []
		for l in prims_collection.keys():
			if prims_collection[l] != 0:
				temp[l] = prims_collection[l]
			else:
				rem_l += [l]
		prims_collection = dict(temp)
	print(res)


def Factor(n):
	Ans = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			Ans.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		Ans.append(n)
	return Ans
t = int(input())
for i in range(t):
	n = int(input())
	m = Factor(n)
	res = 0
	while len(m) > 0:
		i = 0
		prev = 0
		tmp = 1
		while i < len(m):
			if m[i] != prev:
				tmp = tmp * m[i]
				prev = m[i]
				m.pop(i)
			else:
				i = i + 1
		res = res + tmp
	print(res)