Với mỗi số nguyên dương ~n~ cho trước, hãy tìm số nguyên dương ~k~ không vượt quá ~n~ sao cho ~k~ có nhiều ước nguyên tố phân biệt nhất. Nếu có nhiều số ~k~ như vậy thì chọn số ~k~ lớn nhất.

(Ở đây "số lượng ước nguyên tố của ~k~" là số các số nguyên tố khác nhau chia hết ~k~.)

Dữ liệu

• Dòng đầu chứa số nguyên dương ~t~ (~1 \le t \le 10^5~) là số câu hỏi.
• ~t~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên dương ~n~ (~1 \le n \le 10^6~) của câu hỏi thứ ~i~.

Kết quả

• In ra ~t~ dòng, dòng thứ ~i~ là số nguyên dương ~k~ tìm được cho câu hỏi thứ ~i~.

Ví dụ

KMAX.INP

4
8
30
13
4

KMAX.OUT

6
30
12
4

Giới hạn

• Subtask 1 (30% số điểm): ~T \le 100, n \le 500~.
• Subtask 2 (30% số điểm): ~T = 1~.
• Subtask 3 (40% số điểm): không có ràng buộc thêm.