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.


hide comments
[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

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