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²⁰¹⁴, N are 2¹²⁸-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⁶⁴.

Edit 2017-02-11 : TL updated ; compiler changes