Prime Divisor Spell

In the enchanted land of Algebria, magic and numbers intertwine in mysterious ways. The Grand Magus has discovered that the secret to powerful spells lies in the prime factors of certain enchanted numbers. For this task, you are given an integer $n$. Your mission is to compute the sum of all the unique prime divisors of $n$. Formally, if
$n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k},$
where $p_1, p_2, \dots, p_k$ are prime numbers, then you need to find
$S = p_1 + p_2 + \cdots + p_k.$

Should $n$ have no prime divisors (i.e. when $n = 1$), display $-1$ instead.

Input Format

• The first line of input contains an integer $T$, the number of test cases.
• Each of the next $T$ lines contains a single integer $n$.

It is guaranteed that:

• $1 \leq T \leq 10^5$
• $1 \leq n \leq 10^6$

Output Format

For each test case, output a single line containing the sum of the unique prime divisors of $n$. If $n$ has no prime divisors, print $-1$.

Examples

Input

3
1
8
20

Output

-1
2
7

Input

2
15
14

Output

8
9