Coins#11037
When no one plays the machine with its game and Ralph gets bored, he goes out for a walk and collecting coins. For all the time he has already collected as many as n^2 pieces. Despite his appearance, he also likes neatness, so he put them all in a square n \times n, one coin per cell, so that there was no free space in the square.
However, Felix unexpectedly came to visit Ralph and brought another coin. Our hero was extremely happy with such attention and surprise, but he had absolutely no idea where to put it now. So he decided to change the place to store the coins and put all n^2 + 1 coins in another rectangle. However, not everything is so simple, because Ralph is not only neat, but also picky. Namely, he wants the new rectangle x \times y, where his coins are stored, to satisfy the following conditions:
* The rectangle contains all the coins and does not contain empty spaces, i.e. x \times y = n^2 + 1; * The perimeter of the rectangle is as large as possible; * Each side of the rectangle must be at least long.
Based on the value of , Ralph wants to find the treasured numbers and , and as soon as possible - the production of the rectangle needs to start now. Help him!
The first line contains the number of tests (1 \leq q \leq 10^6). The -th of the next lines contains the size n_i (1 \leq n_i \leq 10^6) of the original coin rectangle.
Print lines, -th of which should contain two numbers x_i and y_i (x_i \leq y_i) - the dimensions of the new rectangle or if the rectangle that satisfies the conditions of the problem does not exist.
Example 1
In the test example, the numbers 1^2 + 1 = 2, 2^2 + 1 = 5 and 4^2 + 1 = 17 are prime, and such a number of coins cannot be placed in a rectangle that satisfies the conditions of the problem.
3^2 + 1 = 10 and 5^2 + 1 = 26 the coins can be placed in the rectangle in only one way, and 18^2 + 1 = 325 coins can be put in two ways:
* 5 \times 65, perimeter ; * 13 \times 25, perimeter .
In the first case, the perimeter is bigger, so this is the answer.