Dukker is top in his class. To prove this he always used to participate in math competition. This time in math competition he was given a number(N) and asked to write the prime factorization of N in given way:-

      N = P1e1 * P2e2 * P3e3 * ... * Pkek

where P₁, P₂, P₃ ... P_k are distinct primes arranged in non decreasing order and e₁, e₂, e₃ ... e_k are powers to P₁, P₂, P₃ ... P_k respectively.

Dukker was asked to write only e₁ and P_k. This time Dukker has to go for Holi vacation so he asks for your help.

Input

First line of input contain T (T <= 100000). T is number of test cases and following T lines will contain N (2 <= N <= 1000000).

Output

For each test cases output a single line containing space separated e₁ and P_k.

Example

Input:
3
30
13
20

Output:
1 5
1 13
2 5