Your friends Alice and Bob are very secretive people. Whenever they send a message to each other they encrypt it using the RSA algorithm. For the algorithm to work, Alice and Bob must each pick two prime numbers p and q and from these two numbers they can follow the RSA procedure to generate their own public and private key.

To send an encrypted message to Alice, Bob would have to take her public-key and encrypt his message with it; the only way to decrypt this message is with the private-key that Alice has. A part of the public-key that Alice releases is the cryptographic modulus: n = pq. Since Alice's super secretive private-key is determined solely from the values of p and q, if we were to recover these values we could break her encryption!

Your job is simple: given Alice's modulus help us break her encryption.

Input

The input will begin with a line containing a single positive integer t representing the number of modulus values you must process. Following will be t lines each containing a value x (x ≤ 1,000,000) which is guaranteed to have only two prime factors.

Output

For each modulus print "p q" (where p ≤ q) on its own line.

Example

Input:
4
10
14
77
187

Output:
2 5
2 7
7 11
11 17