Perfect Power Detection

You are given an integer \(n\). Your task is to determine whether \(n\) is a perfect power, i.e. whether there exist integers \(x > 1\) and \(y > 1\) such that \(x^y = n\). If such a pair exists, output one valid pair \(x\) and \(y\); otherwise, output \(-1\).

For example, if \(n = 16\), one valid answer is \(2\) and \(4\) since \(2^4 = 16\). For \(n = 27\), one valid answer is \(3\) and \(3\) since \(3^3 = 27\). If multiple answers are possible, any valid pair is acceptable.

inputFormat

The first line of input contains an integer \(T\) (the number of test cases). Each of the next \(T\) lines contains a single integer \(n\) which you need to check.

outputFormat

For each test case, output on a separate line either two space-separated integers \(x\) and \(y\) if a valid perfect power representation exists, or \(-1\) if no such representation exists.

3
16
27
14

2 4
3 3
-1