Cho dãy số nguyên dương \(A = (a_1, a_2, . . ., a_n)\). Hãy tìm tập nhiều phần tử nhất có cùng ít nhất
một ước số chung lớn lớn hơn 1 và đưa ra số phần tử trong tập tìm được.

Ví dụ, với \(A = (6, 15, 10, 42)\), tập {\(6, 10, 42\)} chứa các số cùng chia hết cho 2 và là tập nhiều phần
tử nhất có cùng ít nhất một ước số chung lớn lớn hơn 1. Số lượng các phần tử trong tập là 3.

Input

• Dòng đầu tiên chứa số nguyên \(n\ (1 \le n \le 1000)\),
• Dòng thứ 2 chứa \(n\) số nguyên \(a_1, a_2, . . ., a_n (2 \le a_i \le 10^{18}, i = 1 ÷ n)\).

Output

• Đưa ra một số nguyên – số lượng phần tử của tập tìm được.

Example

4
6 15 10 42

3