Alice đang nghiên cứu một hệ thống vật lý và muốn khảo sát quá trình chuyển hóa giữa các mức năng lượng của các hạt. Mức năng lượng của hệ thống được biểu diễn bằng một số nguyên dương ~e~. Alice có thể biến đổi mức năng lượng ~e~ bằng các thao tác cơ bản sau:

• Hấp thụ năng lượng: Chuyển từ mức năng lượng ~e~ thành ~e \times p~ (với ~p~ là một số nguyên tố).

• Giải phóng năng lượng: Chuyển từ mức năng lượng ~e~ thành ~e/p~ (với ~p~ là một ước số nguyên tố của ~e~).

Mỗi thao tác hấp thụ hoặc giải phóng năng lượng được tính là ~1~ bước biến đổi. Gọi ~f(e_1,e_2)~ là số bước biến đổi ít nhất để chuyển mức năng lượng từ ~e_1~ thành ~e_2~.

Yêu cầu: Alice hiện có ~N~ mức năng lượng ~A_1,A_2,\dots,A_N~. Với mỗi mức năng lượng ~A_i~ ~(1 \le i \le N)~, Alice muốn tìm một chỉ số ~j~ ~(1 \le j \le N; j \ne i)~ sao cho số bước biến đổi ~f(A_i,A_j)~ đạt giá trị nhỏ nhất. Nếu có nhiều chỉ số ~j~ thỏa mãn cùng cho số bước biến đổi ~f(A_i,A_j)~ nhỏ nhất, Alice ưu tiên chọn chỉ số ~j~ nhỏ nhất.

Input

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

• Dòng thứ hai chứa ~N~ số nguyên ~A_1,A_2,\dots,A_N~ ~(A_i \le 10^6)~.

Output

Gồm ~N~ dòng, dòng thứ ~i~ ~(1 \le i \le N)~ chứa hai số nguyên cách nhau bởi một khoảng trắng lần lượt là số bước biến đổi tối thiểu ~f(A_i,A_j)~ và chỉ số ~j~ tương ứng tìm được.

Scoring

Sample Input 1

2
6 25

Sample Output 1

4 2
4 1

Sample Input 2

3
6 5 25

Sample Output 2

3 2
1 3
1 2