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*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.

Dữ liệu vào:

+ 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 \leq 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 \leq n \leq \ 10^{18})\).

Kết quả:

+ Ghi \(t\) dòng là các đáp án tương ứng.

Ràng buộc:

+ Có 20% số điểm tương ứng với \(t \leq 10^{3}\) và \(n \leq 10^{4}\);

+ Có 80% số điểm còn lại không có ràng buộc gì thêm.