Cho tập hợp ~S~ gồm một số các số nguyên dương. Hãy tìm một tập con ~S' \subseteq S~ thoả mãn:

• ~\forall x, y \in S': x \neq y \Longrightarrow gcd(x, y) = 1~

• ~|S'|~ là lớn nhất

Input

Nhập vào file COPRIME.INP:

• Dòng ~1~: số nguyên dương ~|S|~

• Dòng ~2 \rightarrow |S| + 1~: mỗi dòng gồm một số nguyên dương, miêu tả một phần tử trong tập hợp ~S~

Output

Xuất ra file COPRIME.OUT một số nguyên duy nhất là lực lượng lớn nhất của tập con ~S'~ thoả mãn.

Scoring

Sample Input 1

5
30
2
15
5
6

Sample Output 1

2

Notes

• ~S = \{30, 2, 15, 5, 6\}~

• ~S' = \{5, 6\}~