Cho \(q\) truy vấn, mỗi truy vấn cho số nguyên \(n\). Hãy in ra ước nguyên tố nhỏ nhất (SPF) của \(n\). Nếu \(n\) là số nguyên tố, in ra chính nó.

Định dạng đầu vào

• Dòng đầu: số nguyên \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp: mỗi dòng \(n\) (\(2 \le n \le 10^7\)).

Định dạng đầu ra

• \(q\) dòng, mỗi dòng là SPF của \(n\) tương ứng.

Ví dụ

Input:

3
12
7
100

Output:

2
7
2

Ràng buộc

• 100% số điểm: \(n \le 10^7\), \(q \le 10^5\).