Gabriel is a student from UFPE that loves acai (he really loves it). As he is really passionate about it, he became very picky about how much acai a perfect bowl should have.
A bowl is said to be perfect if the volume of acai in it is a perfect number.
A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself.
Gabriel decided to go to different restaurants and ask how much acai they have. Your task is to help him get the biggest perfect bowl on each of them or declare it is impossible.
The first line of input contains an integer $n$ ($1 <= n <= 2 dot.op 10^6$), the number of restaurants Gabriel will visit. Each of the next $n$ lines contains an integer $k_i$ ($1 <= k_i <= 2 dot.op 10^6$), the amount of acai the $i$-th restaurant has.
Output should consist of $n$ lines. The $i$-th of them must contain an integer $a_i$, the biggest acai Gabriel can have at the $i$-th restaurant, or $-1$ if it's not possible to have a perfect acai.
## Input
The first line of input contains an integer $n$ ($1 <= n <= 2 dot.op 10^6$), the number of restaurants Gabriel will visit. Each of the next $n$ lines contains an integer $k_i$ ($1 <= k_i <= 2 dot.op 10^6$), the amount of acai the $i$-th restaurant has.
## Output
Output should consist of $n$ lines. The $i$-th of them must contain an integer $a_i$, the biggest acai Gabriel can have at the $i$-th restaurant, or $-1$ if it's not possible to have a perfect acai.
[samples]
## Note
In the first example, the answer is $6$, since it's the biggest perfect number lower than or equal to $8$. List of divisors of $8$, excluding itself => $[ 1, 2 ]$ List of divisors of $7$, excluding itself => $[ 1 ]$ List of divisors of $6$, excluding itself => $[ 1, 2, 3 ]$ In the second example, the answer is $-1$, since we don't have any perfect number lower than or equal to $5$. List of divisors of $5$, excluding itself => $[ 1 ]$ List of divisors of $4$, excluding itself => $[ 1, 2 ]$ List of divisors of $3$, excluding itself => $[ 1 ]$ List of divisors of $2$, excluding itself => $[ 1 ]$ List of divisors of $1$, excluding itself => $[ ]$
**Definitions**
Let $ \mathbb{P} \subset \mathbb{Z}^+ $ be the set of perfect numbers:
$$ \mathbb{P} = \left\{ m \in \mathbb{Z}^+ \,\middle|\, \sigma(m) - m = m \right\} = \left\{ m \in \mathbb{Z}^+ \,\middle|\, \sigma(m) = 2m \right\} $$
where $ \sigma(m) $ is the sum of positive divisors of $ m $.
**Given**
- $ n \in \mathbb{Z} $, $ 1 \le n \le 2 \cdot 10^6 $: number of restaurants.
- For each $ i \in \{1, \dots, n\} $, $ k_i \in \mathbb{Z} $, $ 1 \le k_i \le 2 \cdot 10^6 $: acai amount at restaurant $ i $.
**Objective**
For each $ i \in \{1, \dots, n\} $, find:
$$ a_i = \max \left\{ p \in \mathbb{P} \,\middle|\, p \le k_i \right\} $$
If no such $ p $ exists, output $ -1 $.