Món quà dễ thương

An muốn tặng một món quà cho Chi nhân ngày Quốc tế Phụ nữ. An có một dãy số $a_1, a_2, \ldots, a_n$ để dùng cho dịp này và anh ấy quyết định cắt dãy của mình thành hai phần và đưa cho cô ấy một phần. Cụ thể, An muốn chọn một số nguyên $l$ ($1 \le l < n$) và tách dãy thành hai phần, phần đầu là dãy tiền tố độ dài $l$: $a_1, a_2, \ldots, a_l$ và phần sau là dãy hậu tố độ dài $n - l$: $a_{l+1}, a_{l+2}, \ldots, a_n$.

An muốn món quà của mình thật dễ thương. Anh ấy nghĩ rằng món quà sẽ rất dễ thương nếu tích của các phần tử trong phần của Chi nguyên tố cùng nhau với tích của các phần tử trong phần của anh ấy, tức là ước chung lớn nhất của hai tích $a_1 \times a_2 \times \ldots \times a_l$ và $a_{l+1} \times a_{l+2} \times \ldots \times a_n$ bằng 1.

Bạn hãy giúp An tìm ra vị trí nhỏ nhất để cắt dãy, tức là tìm giá trị $l$ nhỏ nhất sao cho món quà của An sẽ dễ thương.

Vào từ tệp văn bản gift.inp. Dòng đầu tiên chứa số nguyên $n$ ($2 \le n \le 10^5$) là số phần tử của dãy số. Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($2 \le a_i \le 10^5$) là các phần tử của dãy số. Dữ liệu vào đảm bảo luôn tồn tại cách cắt dãy.

Ghi ra tệp văn bản gift.out một dòng chứa số nguyên $l$ là vị trí mà An sẽ cắt dãy.

• Có 25% số test ứng với 25% số điểm thoả mãn: $2 \le n \le 10$ và $2 \le a_i \le 10$;
• 25% số test khác ứng với 25% số điểm thoả mãn: $2 \le n \le 100$;
• 25% số test khác ứng với 25% số điểm thoả mãn: $2 \le n \le 1000$;
• 25% số test còn lại ứng với 25% số điểm: Không có thêm ràng buộc nào.