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⁷, 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". N is log-uniform distributed between 2³³³³³ 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.