Cho dãy $n$ số nguyên dương, tìm tập con có số lượng phần tử lớn nhất sao cho GCD của tập này lớn hơn 1.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên $n$ (1 ≤ $n$ ≤ 1000)
• Dòng thứ hai chứa n số nguyên dương ai (2 ≤ $n$ ≤ ${10}^{18}$)

Kết quả:

• Một số nguyên duy nhất là số lượng phần tử của tập con lớn nhất thỏa mãn.

Ví dụ:

INP

4
6 15 10 42

OUT

3