Mọi số tự nhiên ngoài 0 và 1 ra thì chia ra hai loại là hợp số và số nguyên tố. Hợp số là những số có ít nhất 3 ước tự nhiên khác nhau còn số nguyên tố chỉ có đúng hai ước số tự nhiên là 1 và chính nó. Toto học lập trình về vòng lặp được thầy giáo cho bài toán sau. Cho số tự nhiên \(n (2 \leq n \leq 10^9)\) nếu n là hợp số thì in ra ước lớn nhất nhỏ hơn nó còn ngược lại in ra nó là số nguyên tố.

Input

Dòng đầu là số bột test \(t (1 \leq t \leq 100)\)

Tiếp theo gồm t dòng mỗi dòng một số tự nhiên nằm trong đoạn \([2 , 10^9]\)

Output

Đối với mỗi trường hợp kiểm thử xuất ra trên từng dòng

Nếu n nguyên tố xuất ra giá trị của n và "la nguyen to"

Ngược lại xuất ra giá trị của n "la hop so vi chia het cho" theo sau là ước lớn nhất nhỏ hơn n của n

Ví dụ

Input

3
1234523
1234517
24

Output

1234523 la hop so vi chia het cho 72619
1234517 la nguyen to
24 la hop so vi chia het cho 12