Một cặp số giai thừa của một số ~N~ là một cặp ~(x, y)~ nguyên dương bất kỳ sao cho ~x > y~ và

$$ \frac{x!}{y!} = N $$

Với một số ~N~ cho trước, hãy đưa ra một cặp số giai thừa ~(x, y)~ của ~N~ sao cho ~x~ bé nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên dương ~Q~ (~1 \leq Q \leq 10^5~) là số lượng truy vấn bạn cần trả lời.
• ~Q~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~N~ duy nhất (~2 \leq N \leq 10^9~).

Output

Với mỗi truy vấn ghi lần lượt hai số nguyên dương ~x~, ~y~ trên một dòng cho biết cặp số thoả điều kiện đề bài.

Có thể chứng minh rằng đáp án luôn tồn tại với giới hạn của đề bài.

Sample input

2
12
42

Sample output

4 2
7 5

Subtask

• ~30\%~ số test có ~1 \leq Q, N \leq 100~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.