Hôm nay, lớp của Quân làm bài tập môn Toán về nội dung đưa thừa số ra ngoài dấu căn. Bằng kiến thức đã học Quân biết rằng với mọi số tự nhiên \(a > 0\) luôn luôn phân tích được dưới dạng \(\sqrt{a}=\sqrt{x^2\cdot y}=x\sqrt{y}\) với \(x\) gọi là phần nguyên, \(y\) gọi là phần dưới dấu căn (\(x, y\) nguyên dương).

Ví dụ: \(\sqrt{8}=\sqrt{2^2\cdot 2}=2\sqrt{2}\); \(\sqrt{7}=\sqrt{1^2\cdot 7}=1\sqrt{7}\); \(\sqrt{4}=\sqrt{2^2\cdot 1}=2\sqrt{1}\)

Em hãy viết chương trình giúp Quân giải quyết bài toán đưa ra phần nguyên \(x\) và phần dưới dấu căn \(y\) của \(\sqrt{a}\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^3\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a\) (\(1 \le a \le 10^9\)).

Output

• Ghi ra \(N\) dòng, mỗi dòng chứa hai số nguyên dương \(x\) và \(y\) thỏa mãn yêu cầu bài toán.

Example

3
8
7
4

2 2
1 7
2 1

Scoring

• \(60\%\) số test với \(1 \le N \le 10^2; 1 \le a \le 10^4\).
• \(30\%\) số test với \(10^2 < N \le 10^3; 10^4 < a \le 10^6\).
• \(10\%\) số test với \(N \le 10^3; 10^6 < a \le 10^9\).