SP22086 PRIMEPOW - Prime Power Test

[Finite fields](http://en.wikipedia.org/wiki/Finite_field) only exist when the order (size) is a prime power _p $ ^{k} $_ (where p is a prime number and k is a positive integer). For each prime power, there is a finite field with this size, and all fields of a given order are isomorphic. Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory.

The first line contains an integer _T_, the number of test cases. On the next _T_ lines, you will be given an integer _N_ : a proposed order to be tested.

Output _T_ lines, one for each test case, with _p k_ if _N_ can be the order of a finite field. _p_ must be a prime number, and _k_ an integer such that _N_=_p $ ^{k} $_ . Else output "Invalid order".