Short Task (Codeforces 1512G)
Tags: Math, number theory

Let us denote by $$$d(n)$$$ the sum of all divisors of the number $$$n$$$, i.e. $$$d(n) = \sum\limits_{k | n} k$$$.For example, $$$d(1) = 1$$$, $$$d(4) = 1+2+4=7$$$, $$$d(6) = 1+2+3+6=12$$$.For a given number $$$c$$$, find the minimum $$$n$$$ such that $$$d(n) = c$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.Each test case is characterized by one integer $$$c$$$ ($$$1 \le c \le 10^7$$$).

Output: For each test case, output:   "-1" if there is no such $$$n$$$ that $$$d(n) = c$$$;  $$$n$$$, otherwise. 


Sample Inputs:
12
1
2
3
4
5
6
7
8
9
10
39
691

Sample Outputs:
1
-1
2
3
-1
5
4
7
-1
-1
18
-1

Solution (Python):
import sys
input = sys.stdin.readline

def euclid_sieve(n):
    lp = (n + 1) * [0]
    primes = []
    i = 2
    while i <= n:
        if lp[i] == 0:
            primes.append(i)
            lp[i] = i
        for p in primes:
            if p > lp[i] or i * p > n:
                break
            lp[i * p] = p
        i += 1
    return lp
MAX = int(10000000.0)
lp = euclid_sieve(MAX)
divsum = (MAX + 1) * [0]
revsum = (MAX + 1) * [-1]
divsum[1] = 1
revsum[1] = 1
for i in range(2, MAX + 1):
    if lp[i] == i:
        divsum[i] = i + 1
    else:
        v = i
        si = 1
        while v % lp[i] == 0:
            v //= lp[i]
            si = si * lp[i] + 1
        divsum[i] = si * divsum[v]
for i in range(MAX, 1, -1):
    if divsum[i] <= MAX:
        revsum[divsum[i]] = i
t = int(input())
print('\n'.join([str(revsum[int(input())]) for _ in range(t)]))

Solution (Python):
import sys
input = sys.stdin.readline

def euclid_sieve(n):
    lp = (n + 1) * [0]
    primes = []
    i = 2
    while i <= n:
        if lp[i] == 0:
            primes.append(i)
            lp[i] = i
        for p in primes:
            if p > lp[i] or i * p > n:
                break
            lp[i * p] = p
        i += 1
    return lp
MAX = int(10000000.0)
lp = euclid_sieve(MAX)
divsum = (MAX + 1) * [0]
revsum = (MAX + 1) * [-1]
divsum[1] = 1
revsum[1] = 1
for i in range(2, MAX + 1):
    if lp[i] == i:
        divsum[i] = i + 1
    else:
        v = i
        si = 1
        while v % lp[i] == 0:
            v //= lp[i]
            si = si * lp[i] + 1
        divsum[i] = si * divsum[v]
for i in range(MAX, 1, -1):
    if divsum[i] <= MAX:
        revsum[divsum[i]] = i
t = int(input())
for case in range(t):
    print('\n'.join([str(revsum[int(c)]) for c in input().split()]))

Solution (Python):
import collections
import itertools
mod = 10 ** 9 + 7

def permutationbysum():
    for _ in range(int(input())):
        (num, l, r, achieve) = map(int, input().split())
        k = r - l + 1
        if k * (k + 1) // 2 <= achieve <= k * (num * 2 + 1 - k) // 2:
            outpos = r % num
            inpos = l - 1
            ans = [0] * num
            for i in range(num, 0, -1):
                if achieve - i > 0 or (achieve - i == 0 and inpos == r - 1):
                    achieve -= i
                    ans[inpos] = i
                    inpos += 1
                else:
                    ans[outpos] = i
                    outpos += 1
                    outpos %= num
            print(*ans)
        else:
            print(-1)

def peaks():
    for _ in range(int(input())):
        (num, peak) = map(int, input().split())
        pos = 1
        rpos = num
        ans = []
        now = 0
        if num == 1:
            if not peak:
                print(1)
            else:
                print(-1)
            continue
        if num == 2:
            if peak:
                print(-1)
            else:
                print(1, 2)
            continue
        added = 0
        while rpos + 1 != pos:
            if not peak:
                while pos <= rpos:
                    ans.append(pos)
                    pos += 1
                break
            if not now:
                ans.append(pos)
                pos += 1
            else:
                ans.append(rpos)
                rpos -= 1
                if num - added != 1:
                    peak -= 1
            added += 1
            now = 1 - now
        if peak:
            print(-1)
            continue
        print(*ans)
import sys
input = sys.stdin.readline

def addone():
    for _ in range(int(input())):
        (num, changes) = input().split()
        l = collections.deque(sorted([int(i) for i in num]))
        perm = collections.deque()
        changes = int(changes)
        cd = 0
        ans = len(num)
        while True:
            nextnum = l.pop()
            while perm and perm[-1] == nextnum:
                l.append(perm.pop())
            c = 10 - nextnum - cd
            changes -= c
            cd += c
            if changes >= 0:
                if not c:
                    perm.appendleft(1 - cd)
                    l.appendleft(-cd)
                else:
                    l.appendleft(1 - cd)
                    l.appendleft(-cd)
                ans += 1
            else:
                break
        print(ans % 1000000007)
import math

def andsequences():

    def mapping(num):
        nonlocal mnum
        nonlocal c
        num = int(num)
        if num < mnum:
            mnum = num
            c = 1
        elif num == mnum:
            c += 1
        return num
    mod = 1000000007
    for _ in range(int(input())):
        mnum = float('inf')
        c = 0
        num = int(input())
        l = list(map(mapping, input().split()))
        for i in l:
            if mnum & i != mnum:
                print(0)
                break
        else:
            if c == 1:
                print(0)
            else:
                print(math.factorial(num - 2) * (c - 1) * c % mod)

def numberdigit():
    n = 10 ** 5 * 2
    l = [0] * 11
    mod = 10 ** 9 + 7
    l[0] = l[1] = l[2] = l[3] = l[4] = l[5] = l[6] = l[7] = l[8] = 2
    l[9] = 3
    l[10] = 4
    for i in range(11, n):
        l.append((l[i - 10] + l[i - 9]) % mod)
    for _ in range(int(input())):
        (num, c) = input().split()
        c = int(c)
        ans = 0
        for i in num:
            i = int(i)
            if 10 - i > c:
                ans += 1
            else:
                ans += l[c - (10 - i)]
        print(ans % mod)

def mushroom():
    (people, t1, t2, percent) = map(int, input().split())
    l = []
    percent = 1 - percent * 0.01
    for i in range(1, people + 1):
        (s, s1) = map(int, input().split())
        l.append([i, max(s * t1 * percent + s1 * t2, s1 * t1 * percent + s * t2)])
    l.sort(key=lambda x: x[1], reverse=True)
    for i in l:
        i[1] = '{:.2f}'.format(i[1])
        print(*i)

def escape():
    prins = int(input())
    dra = int(input())
    start = int(input())
    pack = int(input())
    c = int(input())
    speeddiff = dra - prins
    if speeddiff <= 0:
        return 0
    pd = start * prins
    ans = 0
    while pd < c:
        hs = pd / speeddiff
        pd += prins * hs
        if pd >= c:
            break
        time = pd / dra
        time += pack
        pd += prins * time
        ans += 1
    return ans

def perm():

    def high(n, k):
        return k * (2 * n - k + 1) // 2

    def low(k):
        return k * (k + 1) // 2
    for _ in range(int(input())):
        (num, lef, rig, s) = map(int, input().split())
        k = rig - lef + 1
        (rig, lef) = (rig - 1, lef - 1)
        if not high(num, k) >= s >= low(k):
            print(-1)
            continue
        l = [0] * num
        lp = lef
        rp = lef - 1
        for i in range(num, 0, -1):
            if high(i, k) >= s and s - i >= low(k - 1) and k:
                l[lp] = i
                lp += 1
                s -= i
                k -= 1
            else:
                l[rp] = i
                rp -= 1
        if k:
            print(-1)
        else:
            print(*l)

def newcom():
    for _ in range(int(input())):
        (days, price) = map(int, input().split())
        dl = input().split()
        worth = input().split()
        worth.append(0)
        ans = float('inf')
        req = 0
        left = 0
        for i in range(days):
            a = int(dl[i])
            w = int(worth[i])
            ans = min(ans, req + max(0, price - left + a - 1) // a)
            ns = max(0, w - left + a - 1) // a
            req += ns + 1
            left += a * ns - w
        print(ans)

def perfectsq():
    for _ in range(int(input())):
        n = input()
        for i in input().split():
            sq = math.sqrt(int(i))
            if sq != int(sq):
                print('YES')
                break
        else:
            print('NO')

def comb(n, c):
    return math.factorial(n) // (math.factorial(c) * math.factorial(n - c))

def and0big():
    for _ in range(int(input())):
        (l, k) = map(int, input().split())
        print(l ** k % mod)
import math

def mod1p():
    n = int(input())
    ans = dict()
    p = 1
    for i in range(1, n):
        if math.gcd(i, n) == 1:
            ans[str(i)] = True
            p = p * i % n
    if p == 1:
        print(len(ans))
        print(' '.join(ans.keys()))
    else:
        ans.pop(str(p))
        print(len(ans))
        print(' '.join(ans.keys()))

def shorttask():
    num = 10000100
    l = [-1] * (num + 2)
    s = [-1] * (num + 2)
    l[1] = 1
    for i in range(2, int(math.sqrt(num + 1)) + 2):
        if l[i] == -1:
            l[i] = i
            for x in range(i * i, num + 1, i):
                if l[x] == -1:
                    l[x] = i
    s[1] = 1
    for i in range(2, num + 1):
        if l[i] == -1:
            l[i] = i
            s[i] = i + 1
        else:
            i1 = i
            s[i] = 1
            while i1 % l[i] == 0:
                i1 //= l[i]
                s[i] = s[i] * l[i] + 1
            s[i] *= s[i1]
    ans = [-1] * (num + 1)
    for i in range(num, 0, -1):
        if s[i] < num:
            ans[s[i]] = i
    for _ in range(int(input())):
        print(ans[int(input())])
shorttask()