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\le n\le {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\le t\le 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