CF1512G Short Task

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 $ .

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 $ ).

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