PRIMEPOW  Prime Power Test
Finite fields 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.
Input
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
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".
Example
Input: 3 6 7 8 Output: Invalid order 7 1 2 3
Constraints
For the hardest input files : T about 100, and 1 < N < 2^{2014}, N are 2^{128}smooth numbers. (Thanks at Min_25 for suggesting this constraint). About 50% of input cases are "Invalid order".
For the easiest input files : T about 10000, and 1 < N < 2^{64}.
Edit 20170211 : TL updated ; compiler changes
hide comments
Michael Kharitonov:
20170202 21:38:42
@Francky, how close am I to AC? My first Python code in a long time.


testing java:
20170103 22:29:05
It is really frustrating. I don't even know whether there is some bug in code (I don't use python everyday, but this problem forced me to use it, thus some bugs are likely), or is my primality test not good enough for given testcases. Right now, can't find any counterexample to work with.


copperfield42:
20160920 01:13:44
I only register to solve this and it was a fun little problem, not bad for my first try this site, I guess.


[Lakshman]:
20160627 10:31:15
I tried this problem again with different logic and tested it on ideone with random test cases it is taking around 10s on ideone for T=100 and n <=(2**2014) here it is giving TLE. (Spoj cluster is 2x faster than ideone).


JY:
20160316 17:52:42
I don't know why I get tle.


Viplov Jain:
20150212 13:25:18
@Francky help with with the WA's. cant find the error


[Lakshman]:
20150123 04:50:20
@Francky can you please publish a tutorial version of this problem with relaxed time limit. Thanks.


[Lakshman]:
20150111 06:26:44
@Francky Can you please tell me about two of my submission for #13396009 can we get AC with this method.


[Lakshman]:
20141223 19:37:29
@Francky can you please have a look on my last submission now I am getting wrong answer.


[Lakshman]:
20141214 16:12:44
@Francky any suggestion for optimization?

Added by:  Francky 
Date:  20141212 
Time limit:  1s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Number theory 