Số nguyên tố là số chỉ chia hết cho và chính nó. Cho số nguyên \(n\) hãy kiểm tra xem \(n\) có dạng lũy thừa của một số nguyên tố hay không? Nếu phải thì in ra cơ số và lũy thừa, còn không thì in \(0\) .

Input

• Một số nguyên dương \(n\)

Output

• Nếu đúng điều kiện thì in ra cơ số và lũy thừa, còn không thì in \(0\)

Điều kiện

• \(1 \le n \le 10^{18}\)

Sample Input 1

27

Sample Output 1

3 3