Supernumber

Define the function \(f(x)\) as the number of divisors of \(x\). A positive integer \(n\) is called a supernumber if

\[ \forall i\in [1,n)\cap \mathbb{Z^+},\; f(n)> f(i), \]

In other words, \(n\) is a supernumber if \(f(n)\) is strictly greater than \(f(i)\) for every positive integer \(i<n\). Note that by definition, 1 is a supernumber.

You are given \(m\) numbers \(a_1,a_2,\ldots,a_m\). For each \(a_j\), output the largest supernumber that is \(\le a_j\).

inputFormat

The first line contains a single integer \(m\) indicating the number of queries. Each of the following \(m\) lines contains one integer \(a_j\) \((1\le a_j)\) representing a query.

outputFormat

For each query, print the largest supernumber that does not exceed \(a_j\) on a new line.

sample

3
1
10
100

1
6
60