Số nguyên tố là số nguyên dương lớn hơn 1 chỉ có hai ước số là 1 và chính nó. Với mọi số tự nhiên X (với X>1) đều có ít nhất một ước số nguyên tố. Ví dụ: X=4 có một ước nguyên tố là 2. X=6 có hai ước nguyên tố là 2 và 3.

Yêu cầu: Cho dãy số a gồm n số nguyên dương: a,, a,..,an. Hãy cho biết trong dãy số trên, số nào có nhiều ước số nguyên tố nhất? Nếu có nhiều đáp án thì ghi ra số có thứ tự trong dãy nhỏ nhất thỏa mãn yêu cầu.

Dữ liệu vào: Đọc từ tệp văn bản PRIME.INP gồm hai dòng:

Dòng 1: Chứa một số nguyên dương n là số lượng các phần tử của dãy a (với 2 ≤ n ≤ 10^6)

Dòng 2: Chứa n số nguyên dương a, (2 ≤ a ≤ 10^6, 1 ≤ i ≤ n), mỗi số cách nhau bởi một dấu cách.

Kết quả ra: Ghi ra tệp văn bản PRIME.OUT gồm duy nhất một số nguyên thòa mãn yêu cầu bài toán.

Ràng buộc:

Các test tương ứng với 40% số điểm có: 2 ≤ n ≤ 10^2 và 2 ≤ a ≤ 10^3.

Các test tương ứng với 40% số điểm có: 10^2 < n ≤ 10^5 và 10^3 < a ≤ 10^5.

Các test tương ứng với 20% số điểm: Không có ràng buộc gì thêm.

Input:

6
2 10 6 4 8 15

Output:

10