Given a natural number
N - the number of numbers (1<=N<=10
3), and natural numbers
ai (1<=a
i<=10
5 ). For each number
ai determine the smallest natural number
m less than
ai that has the maximum number of different divisors.
Input
In the first line, the program receives a natural number N (1<=N<=103) as input. The following N lines set the numbers ai (1<=ai<=10 5), each number on a separate line.
Imprint
For each number ai print the number m - the smallest natural number less than ai, which has the maximum number of different divisors. Each number m must be printed on a separate line.
Examples
| # |
Input |
Output |
| 1 |
5
440
552
953
53
175 |
360
360
840
48
120
|