Когда в автомат с его игрой никто не играет и Ральфу становится скучно, он выходить прогуляться и пособирать монетки. За все время он собрал их уже целых n2 штук. Несмотря на свой внешний вид, он также любит аккуратность, поэтому уложил их все в квадрат n * n, по одной монетке в ячейку, так, что свободного места в квадрате не осталось.

Однако, неожиданно к Ральфу в гости пришел Феликс и принес еще одну монетку. Наш герой был безумно рад такому вниманию и сюрпризу, но абсолютно не имел понятия, куда ее теперь положить. Поэтому он решил поменять место для хранения монеток и положить все n2 + 1 монетку в другой прямоугольник. Однако, не все так просто, ведь Ральф не только аккуратен, но и придирчив. А именно, он хочет, чтобы для нового прямоугольника x * y - места хранения его монеток - выполнялись следующие условия:

• Прямоугольник вмещает в себя все монетки и не содержит пустых мест, то есть x * y = n2 + 1;
• Периметр прямоугольника максимально возможный;
• Каждая сторона прямоугольника должна иметь длину хотя бы 2.

По данному n Ральф хочет найти заветные числа x и y, и как можно быстрее - изготовление прямоугольника нужно начинать уже сейчас. Помогите ему!

Входные данные

В первой строке содержится количество тестов q (1 ≤ q ≤ 106). В i-й из следующий q строк содержится размер ni (1 ≤ ni ≤ 106) изначального прямоугольника с монетками.

Выходные данные

Выведите q строк, в i-й из которой должны находиться два числа xi и yi (xi ≤ yi) - размеры нового прямоугольника или -1, если прямоугольника, удовлетворяющего условиям задачи, не существует.

Примечание

В тестовом примере числа 12 + 1 = 2, 22 + 1 = 5 и 42 + 1 = 17 - простые, и такое количество монеток нельзя уложить в прямоугольник, удовлетворяющий условиям задачи.

32 + 1 = 10 и 52 + 1 = 26 монеток уложить в прямоугольник единственным способом, а 182 + 1 = 325 монеток можно уложить двумя способами:

• 5 * 65, периметр 70;
• 13 * 25, периметр 38.

В первом случае периметр больше, поэтому это и будет ответом.