Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

A. Maximize?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer x. Your task is to find any integer y (1y<x) such that gcd is maximum possible.

Note that if there is more than one y which satisfies the statement, you are allowed to find any.

\gcd(a,b) is the Greatest Common Divisor of a and b. For example, \gcd(6,4)=2.

Input

The first line contains a single integer t (1 \le t \le 1000) — the number of test cases.

Each of the following t lines contains a single integer x (2 \le x \le 1000).

Output

For each test case, output any y (1 \le y < x), which satisfies the statement.

Example
Input
7
10
7
21
100
2
1000
6
Output
5
6
18
98
1
750
3