PRIMPOW2  Prime Power Test (Hard)
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
T about 2^{7}, and 1 < N < 2^{33333}, N are 2^{128}smooth numbers. (Thanks at Min_25 for suggesting this constraint).
About 50% of input cases are "Invalid order". N is loguniform distributed between 2^{33333} and its square root.
Prime numbers in N decomposition are almost loguniform distributed, from 4bit to 128bit. 3 input files.
You may first try PRIMEPOW with easier constraints.
Edit(20170211) TL updated ; compiler changes.
hide comments
[Lakshman]:
20190113 07:32:00
@francky I did some changes in my old code and got AC in PRIMEPOW and my complexity is quite good


copperfield42:
20160920 19:33:49
@Francky I am stuck, I solve the first one but the same solution don't work here why is that??

Added by:  Francky 
Date:  20141213 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 