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