Description

Let the number of divisors of $x$ be $f(x)$. If $\forall i\in [1,n)\cap \mathbb{Z^+}, f(n)>f(i)$, then we call $n$ a supernumber.

Given $m$ numbers $a_1, a_2, \ldots, a_m$, for each $a_i$, output the largest supernumber not exceeding $a_i$.

Input Format

The first line has one integer representing $m$.

From line $2$ to line $(m+1)$, each line contains one integer, where the integer on line $(i+1)$ is $a_i$.

Output Format

Output $m$ lines, one integer per line, where the $i$-th line is the largest supernumber not exceeding $a_i$.

2
8
13

6
12

Hint

Constraints

• For 40% of the testdata, $m=1$.
• For 50% of the testdata, $a_i\le 1000$.
• For 70% of the testdata, $a_i\le 2\times 10^7$.
• For 100% of the testdata, $m\le 10^5$, $a_i\le 10^{17}$.

Translated by ChatGPT 5