Long là một học sinh chuyên Toán nhưng lại rất đam mê lập trình. Trong một lần Long được học về phép chia có dư đối với các số tự nhiên như sau: Nếu số tự nhiên \(N\) chia \(X\) dư \(R\) thì số \(N\) sẽ được biểu diễn thành dạng sau: \(N = K \times X + R\). Tình cờ được biết sắp tới ở trường chuyên Lam Sơn có tổ chức thi khảo sát chất lượng học sinh giỏi cấp 2, nên Long có bài toán đố các bạn như sau: Cho một số tự nhiên \(N\). Tìm số tự nhiên \(X < N\) sao cho kết quả của phép chia lấy dư \(N\) cho \(X\) là lớn nhất. Vì các bạn lập trình nên sẽ trả lời rất nhanh nên Long sẽ đưa ra \(T\) câu hỏi liên tục để các bạn trả lời.

Input

Vào từ file BAI3.INP gồm

• Dòng đầu tiên chứa số nguyên dương \(T\) là số lượng câu hỏi mà Long đưa ra ( \(T ≤ 10^5\));
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\) là một câu hỏi của Long (\(5 ≤ N ≤ 10^{18}\)).

Output

Ghi ra file BAI3.OUT gồm \(T\) dòng là các đáp án tương ứng..

Scoring

• Có 20% số điểm tương ứng với \(T ≤ 10^3\) và \(N ≤ 10^4\);
• Có 80% số điểm còn lại không có ràng buộc gì thêm.

Example

2
6
9

4
5