NR3 - Dukker The Topper

no tags 

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 P1, P2, P3 ... Pk are distinct primes arranged in non decreasing order and e1, e2, e3 ... ek are powers to P1, P2, P3 ... Pk respectively.

Dukker was asked to write only e1 and Pk. 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 e1 and Pk.

Example

Input:
3
30
13
20

Output:
1 5
1 13
2 5

hide comments
Dushyant Singh: 2015-06-21 22:03:07

Nice!

Rahul Kumar Dahmiwal: 2014-07-12 11:15:05

any tricky test cases


Added by:NISHANT RAJ
Date:2014-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own