Với hai số nguyên dương x,y, ta định nghĩa khoảng cách giữa x và y là số phép nhân với một số nguyên tố hoặc chia hết cho một số nguyên tố để biến số x thành số y.
Ví dụ khoảng cách giữa 100 và 360 bằng 4 vì:
~100/5×2×3×3=360~,với 2,3,5 là các số nguyên tố được chọn tối ưu.

Yêu cầu:

Cho mảng A gồm N phần tử ~a_1, a_2,…,a_n~. Tìm khoảng cách lớn nhất giữa 2 phần tử ~a_i~ và ~a_j~ bất kỳ trong mảng.

Dữ liệu:

Dòng đầu tiên ghi số nguyên N là số phần tử của dãy. ~(2≤N≤10^5)~
Dòng tiếp theo ghi N số nguyên ai là các phần tử của mảng. ~(a_i \le 10^6)~

Kết quả:

Một dòng duy nhất là khoảng cách lớn nhất tìm được.

Sample Input:

5
18 134 232 58 62

Sample Output:

5