Cho số nguyên dương \(N \ge 5\).

Tìm số nguyên dương \(X\) lớn nhất và \(X < N\), sao cho \(N \% X\) đạt giá trị lớn nhất. (\(\%\) là phép chia lấy dư)

Input

• dòng đầu ghi \(Q\) không quá \(10^5\)- số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(N (N \le 10^{18})\)

Output

• Ứng với mỗi câu hỏi, in ra đáp án cần tìm.

Example

2
6
9

4
5