Khi giảng dạy về nội dung ước số chung lớn nhất, Alice đã cho học sinh bài toán sau:

Cho \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hãy chọn ra nhiều số nhất mà ước chung lớn nhất của chúng lớn hơn \(1\).

Ví dụ, với dãy số gồm bốn số \(4, 5, 8, 20\), có thể chọn được nhiều nhất ba số, chọn các số \(4, 8, 20\) có ước chung lớn nhất là \(4\).

Yêu cầu: Cho \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hãy tính số lượng số nhiều nhất chọn được thỏa mãn điều kiện bài toán.

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^{18}\)).

Output

• Ghi ra một số nguyên là số lượng số chọn được.

Example

4
4 5 8 20

3

4
2 4 6 8

4

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n = 2\) và \(a_i \le 10^6\) (\(1 \le i \le n\)).
• Subtask 2 (\(30\%\) số điểm): \(n \le 18\).
• Subtask 3 (\(30\%\) số điểm): \(a_i \le 10^6\) (\(1 \le i \le n\)).
• Subtask 4 (\(20\%\) số điểm): Không có ràng buộc nào thêm.