Hiện tại ở Nghệ An đang có phong trào khởi nghiệp tại quê hương. Một trong những doanh nghiệp startup thành công tại Nghệ An là công ty cổ phần công nghệ Gostream – một công ty chuyên về livestream trên các nền tảng facebook và google. Hiện tại, tài sản của công ty ước tính khoảng 5 triệu đô. Một điều khá thú vị là 2 trong 3 co - founder của công ty là cựu học sinh của trường THPT Chuyên – Đại học Vinh và thú vị hơn thuở còn đi học họ rất mê code. Hưởng ứng phong trào khởi nghiệp trên, một nhóm thanh niên mở công ty chuyên vể sửa điều hòa. Đừng nghĩ đây là việc dễ và ít tiền, mấy hôm nay nhà Mr Toàn hỏng điều hòa nhưng chưa gọi nổi thợ đến sửa đây. Tuy nhiên, không phải lúc nào công việc cũng dễ ăn cả. Hôm nay nhóm các bạn trẻ này gặp một cái điều hòa khá chuối. Chiếc máy điều hòa này phải dùng mật mã để khởi hành. Ở sau máy điều hòa có 1 dãy số gồm n  số nguyên dương ai  và 1 tờ giấy ghi chép rằng: Nếu muốn hưởng mát thì phải tìm ra được số cặp (i, j) với i <j sao cho lcm(ai, aj)*gcd(ai,aj) có chính xác 3 ước số.

Định nghĩa : lcm là bội chung nhỏ nhất, gcd là ước chung lớn nhất.

Bạn hãy giúp nhóm các bạn trẻ giỏi về điện lạnh nhưng lại không giỏi code kia khắc phục tình trạng của chiếc máy điều hòa này nhé.

Đầu vào:

- Dòng đầu tiên gồm số nguyên dương n (n<=10^5).

- Dòng tiếp theo gồm n số nguyên dương ai (0<ai<=10^6)

Đầu ra:

- In ra số cặp (i, j) thỏa mãn yêu cầu bài toán.