## PRIMPOW2 - Prime Power Test (Hard)

no tags

Finite fields only exist when the order (size) is a prime power pk (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=pk. Else output "Invalid order".

### Example

```Input:
3
6
7
8

Output:
Invalid order
7 1
2 3
```

### Constraints

T about 27, and 1 < N < 233333, N are 2128-smooth numbers. (Thanks at Min_25 for suggesting this constraint).
About 50% of input cases are "Invalid order". N is log-uniform distributed between 233333 and its square root.
Prime numbers in N decomposition are almost log-uniform distributed, from 4bit to 128bit. 3 input files.
You may first try PRIMEPOW with easier constraints.

Edit(2017-02-11) TL updated ; compiler changes. [Lakshman]: 2019-01-13 07:32:00 @francky I did some changes in my old code and got AC in PRIMEPOW and my complexity is quite good \$ O(log n (log log n) ^ 2) + K * O(log n log log n) \$ where K is the number of iteration in miller Rabin still I am getting TLE here. =(Francky)=> L.73 It is not a O(1) operation, but costly... You need a better global method. Good luck ;-) Last edit: 2019-01-14 13:49:16 copperfield42: 2016-09-20 19:33:49 @Francky I am stuck, I solve the first one but the same solution don't work here why is that?? =(Francky)=> On your last line, you have #main(). It should be main(). After that, you have to find ideas to avoid TLE. Good luck. @Francky I see, thanks. Any suggestion for that? =(Francky)=> Maybe consider various kind of test case, and try several methods ; maybe... I won't give more clues. Good luck, and have fun ;-) Last edit: 2016-09-21 22:29:25