An là một học sinh giỏi Toán, đặc biệt rất đam mê các bài toán số học. Trong bài tập lần này, thầy giáo giao cho An một bài toán tưởng chừng như rất dễ nhưng lại mang đến cho An một thử thách mới. An nhận được một dãy ~A~ gồm ~N~ số nguyên ~a_1, a_2, \dots a_N~. Bài toán đặt ra là với mỗi ~a_i~ ~(1 \le i \le N)~, hãy tìm số nguyên ~x~ ~(1 \le x \le a_i)~ có số lượng ước nguyên dương lớn nhất. Nếu có nhiều số ~x~ thỏa mãn yêu cầu thì chọn số có giá trị nhỏ nhất. Mặc dù đã giải xong, nhưng An muốn kiểm tra lại kết quả này đã chính xác hay chưa.

Yêu cầu: Là một học sinh giỏi môn Tin học, em hãy lập trình tính kết quả bài toán để giúp An đối chiếu.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^5)~;

• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~a_i~ ~(a_i \le 10^{18})~.

Output

Gồm ~N~ dòng:

• Dòng thứ ~i~ ghi hai số nguyên dương, số thứ nhất là số ~x~ tìm được ứng với số ~a_i~, số thứ hai là số lượng ước nguyên dương của ~x~. Hai số cách nhau một khoảng trắng.

Scoring

Sample Input 1

2
19
200

Sample Output 1

12 6
180 18

Notes

Với ~a_1 = 19~, trong các số từ ~1~ đến ~19~, ta tìm được số ~12~ và ~18~ đều có số lượng ước nhiều nhất là ~6~ ước.