Read problems statements in Mandarin Chinese  and Russian. 

Chef wants to hire a new assistant. He published an advertisement regarding that in a newspaper. After seeing the advertisement, many candidates have applied for the job. Now chef wants to shortlist people for the interviews, so he gave all of them one problem which they must solve in order to get shortlisted.

The problem was : For a given positive integer N, what is the maximum sum of distinct numbers such that the Least Common Multiple of all these numbers is N.  

Your friend Rupsa also applied for the job, but was unable to solve this problem and hence you've decided to help her out by writing a code for solving this problem.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.		
Each test case contains a single integer N.

------ Output ------ 

For each test case, output a single line containing an integer corresponding to the answer for that test case.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{9}$

Subtask 1 (30 points):

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$

Subtask 2 (70 points):

$original constraints$

----- Sample Input 1 ------ 
2

1

2
----- Sample Output 1 ------ 
1

3
----- explanation 1 ------ 
Example 1 : Only possible number is 1, so the maximum sum of distinct numbers is exactly 1. 
Example 2 : The distinct numbers you can have are just 1 and 2, so the sum is 3. If we consider any other number greater than 2, then the least common multiple will be more than 2.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			k = n // i
			if k == i:
				c = c + i
			else:
				c = c + i + k
	print(c)


import math
T = int(input())
for x in range(T):
	n = int(input())
	a = 0
	for i in range(1, math.floor(n ** 0.5) + 1):
		if n % i == 0:
			a += i
			o = n // i
			if o != i:
				a += o
	print(a)


import math
for i in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			q = n // i
			if q != i:
				ans += q
			ans += i
	print(ans)


for t in range(int(input())):
	n = int(input())
	sm = 0
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			sm += i
			o = n // i
			if o != i:
				sm += o
	print(sm)


import math
for _ in range(int(input())):
	n = int(input())
	p = int(math.sqrt(n))
	ans = 0
	for i in range(1, p + 1):
		if n % i == 0:
			q = int(n / i)
			if q == i:
				ans += i
			else:
				ans += i + q
	print(ans)


import math

def printDivisors(n):
	c = 0
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				c += i
			else:
				c += i
				c += n / i
		i = i + 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	print(int(printDivisors(n)))


t = int(input())
for _ in range(t):
	n = int(input())
	i = 1
	answer = 0
	while i * i < n:
		if n % i == 0:
			answer += i
			answer += n // i
		i += 1
	if i * i == n:
		answer += i
	print(answer)


import math
for __ in range(int(input())):
	n = int(input())
	if n == 1:
		s = 1
	else:
		s = n + 1
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			s += i
			n2 = n // i
			if n2 != i:
				s += n2
	print(s)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	su = 0
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			su += i + (n // i if i != n // i else 0)
	print(su)


import math
for _ in range(int(input())):
	n = int(input())
	res = 0
	i = 1
	if n == 1:
		print(i)
	else:
		while i <= math.sqrt(n):
			if n % i == 0:
				if n / i == i:
					res += i
				else:
					res += i
					res += n // i
			i += 1
		print(res)


from functools import reduce
from math import sqrt

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
T = int(input())
for I in range(T):
	s = 0
	n = int(input())
	a = []
	s = sum(factors(n))
	print(s)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = 0
	y = int(math.sqrt(n))
	for i in range(1, y + 1):
		if n % i == 0:
			s += i
			if i != n // i:
				s += n // i
	print(s)


from math import sqrt
for _ in range(int(input())):
	N = int(input())
	ans = 0
	for i in range(1, int(sqrt(N)) + 1):
		if N % i == 0:
			p = N // i
			if i == p:
				ans += i
			else:
				ans += i + p
	print(ans)


import math
T = int(input())
for i in range(T):
	n = int(input())
	p = [1]
	s = 0
	j = 2
	c = int(math.sqrt(n))
	d = {1: 1}
	q = 1
	for j in range(1, c + 1):
		if n % j == 0:
			s = s + j
			if n // j != j:
				s = s + n // j
	print(s)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = 1 + n
	for j in range(2, int(math.sqrt(n)) + 1):
		if n % j == 0:
			s += j
			if j != n // j:
				s += n // j
	if n == 1:
		print(1)
	else:
		print(s)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, int(pow(n, 1 / 2)) + 1):
		if n % i == 0:
			if n // i == i:
				ans += i
			else:
				ans += i
				ans += n // i
	print(ans)


import math
T = int(input())
for i in range(T):
	n = int(input())
	sum = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			sum += i
			if n // i != i:
				sum += n // i
	print(sum)


import math

def factorize(n):
	factors = [(i, n // i) for i in range(1, int(math.sqrt(n)) + 1) if n % i == 0]
	factors = [f for fact in factors for f in fact]
	factors = list(set(factors))
	print(sum(factors))
for _ in range(int(input())):
	n = int(input())
	factorize(n)


from math import *
for u in range(int(input())):
	n = int(input())
	s = 0
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			s += n // i
			if n // i != i:
				s += i
	print(s)


test = int(input())
for _ in range(test):
	n = int(input())
	s = 0
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			j = n // i
			if j == i:
				s += i
			else:
				s += i + j
	print(s)


from math import *
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	s = 0
	if n == 2:
		print(3)
	elif n == 3:
		print(4)
	else:
		for i in range(1, int(sqrt(n)) + 1):
			if n % i == 0:
				s += i + int(n / i)
		if int(sqrt(n)) * int(sqrt(n)) == n:
			s -= int(sqrt(n))
		print(s)


t = int(input())
while t != 0:
	x = int(input())
	f = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			f.append(i)
			if x // i != i:
				f.append(x // i)
		i += 1
	print(sum(f))
	t -= 1


for _ in range(int(input())):
	X = 0
	N = int(input())
	T = 1
	while T * T <= N:
		if not N % T:
			X += T
			if T * T != N:
				X += N // T
		T += 1
	print(X)


from math import ceil

def solve(n):
	sumset = set()
	for i in range(1, ceil(n ** 0.5) + 1):
		if n % i == 0:
			sumset.add(i)
			sumset.add(n // i)
	return sum(sumset)

def main():
	for _ in range(int(input())):
		n = int(input())
		ans = solve(n)
		print(ans)
main()


import math

def solution(N):
	sum = 0
	LIM = int(math.sqrt(N))
	for i in range(1, LIM + 1):
		if N % i == 0:
			sum += i
			if N / i != i:
				sum += N / i
	return int(sum)
T = int(input())
for t in range(T):
	print(solution(int(input())))


t = int(input())
for i in range(t):
	n = int(input())
	sum = 0
	for j in range(1, int(n ** (1 / 2)) + 1):
		if n % j == 0:
			sum = sum + j
			if n // j != j:
				sum = sum + n // j
	print(sum)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	root = int(sqrt(n))
	sum = 0
	for i in range(1, root + 1):
		if n % i == 0:
			sum = sum + i
			if i * i != n:
				sum = sum + n / i
	print(int(sum))


import math

def fun(n1, n2, m):
	x = min(n1, n2)
	r = m * (m + 1) // 2
	if r < x:
		return n1 + n2 - 2 * r
	else:
		return max(n1, n2) - x
for _ in range(int(input())):
	n = int(input())
	ans = 0
	if n == 1:
		print(1)
		continue
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			if n // i != i:
				ans += i + n // i
			else:
				ans += i
	print(ans)


from math import *
for i in range(int(input())):
	n = int(input())
	sum = 0
	for j in range(1, int(sqrt(n)) + 1):
		if n % j == 0:
			sum += n // j
			if n // j != j:
				sum += j
	print(sum)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	count = 0
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			count += i
			if n // i != i:
				count += n // i
	print(count)


def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(1)
	elif N == 2:
		print(3)
	else:
		lim = int(N ** 0.5) + 1
		summ = 1 + N
		for i in range(2, lim):
			if N % i == 0:
				tmp2 = N // i
				if i != tmp2:
					summ += i + tmp2
				else:
					summ += i
		print(summ)


import math

def Solve(n):
	sum = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			v = n // i
			if v != i:
				sum = sum + v + i
			else:
				sum = sum + i
	return sum
for _ in range(int(input())):
	n = int(input())
	print(Solve(n))


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		lis = 0
		for i in range(1, int(math.sqrt(n)) + 1):
			if n % i == 0:
				lis += i
				if n // i != i:
					lis += n // i
		print(lis)


import math
tc = int(input())
for ii in range(tc):
	n = int(input())
	c = 0
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			a = i
			b = n // i
			if a == b:
				c += a
			else:
				c += a
				c += b
	print(c)


for _ in range(int(input())):
	n = int(input())
	i = 1
	ans = 0
	while i * i <= n:
		if n % i == 0:
			if i * i == n:
				ans += i
			else:
				ans += i + n // i
		i += 1
	print(ans)


from math import *

def primeFactor(num):
	factor = []
	while num % 2 == 0:
		factor.append(2)
		num = num >> 1
	for j in range(3, int(sqrt(num)) + 1, 2):
		while num % j == 0:
			factor.append(j)
			num = num // j
	if num > 2:
		factor.append(num)
	return factor
times = int(input())
for i in range(times):
	num = int(input())
	if num == 1:
		print(1)
	else:
		factor = primeFactor(num)
		prod = 1
		if len(factor) == 1:
			print(1 + num)
		else:
			repeat = 1
			prevFactor = factor[0]
			for j in range(1, len(factor)):
				if prevFactor != factor[j]:
					prod = prod * ((prevFactor ** (repeat + 1) - 1) // (prevFactor - 1))
					prevFactor = factor[j]
					repeat = 1
				else:
					repeat += 1
			prod = prod * ((prevFactor ** (repeat + 1) - 1) // (prevFactor - 1))
			print(prod)


from math import sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	res = 0
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			res += n // i
			if n // i != i:
				res += i
	print(res)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	li = []
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			li.append(i)
			if n // i not in li:
				li.append(n // i)
	li.sort()
	if n == 1:
		print(1)
	else:
		print(sum(li))


from math import *
t = int(input())
for i in range(t):
	n = int(input())
	sum = 0
	if n == 1:
		print(1)
	else:
		for i in range(1, int(sqrt(n) + 1)):
			if n % i == 0:
				sum = sum + i
				if i != n // i:
					sum = sum + n // i
		print(sum)


T = int(input())
for i in range(T):
	N = int(input())
	s = 0
	for i in range(1, int(N ** (1 / 2)) + 1):
		if N % i == 0:
			j = N // i
			if j == i:
				s += i
			else:
				s += i + j
	print(s)


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


for _ in range(int(input())):
	n = int(input())
	s = 0
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			t = n // i
			if t != i:
				s += t
			s += i
	print(s)


import math
for _ in range(int(input())):
	n = int(input())
	sum = 0
	limit = math.sqrt(n)
	for i in range(1, int(limit) + 1):
		if n % i == 0:
			sum += i
			if i != n // i:
				sum += n // i
	print(int(sum))


import math
for _ in range(int(input())):
	n = int(input())
	s = int(math.sqrt(n))
	(i, a) = (1, 0)
	while i <= s:
		if n % i == 0:
			a += i
			if n != i * i:
				a += n // i
		i += 1
	print(a)


import math

def ans(n):
	s = 0
	r = int(math.sqrt(n))
	for i in range(1, r + 1):
		if n % i == 0:
			if i == n / i:
				s += i
			else:
				s += i
				s += n / i
	print(int(s))
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		ans(n)


def maxsum(n):
	s = 0
	i = 1
	while i * i <= n:
		if n % i == 0:
			s += i
			if n // i != i:
				s += n // i
		i += 1
	return s
n = 12
t = int(input())
for i in range(t):
	n = int(input())
	print(maxsum(n))


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	ans = 0
	for j in range(1, math.floor(num ** 0.5) + 1):
		if num % j == 0:
			ans += j
			other = num // j
			if other != j:
				ans += other
	print(ans)


import math

def factors(n):
	l = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			if i == n / i:
				l += i
			else:
				l += i + n // i
	return l + n + 1
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		print(factors(n))


import math

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		print(int(divSum(n)) + n)