Chọn số

Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\), hãy chọn ra một tập \(S\) nhiều số nhất mà không có hai số nào thuộc tập \(S\) chia hết cho nhau.

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 20\));
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^9\)).

Output

• Gồm một dòng chứa một số là số lượng số chọn thuộc tập \(S\).

Example

2
5 6

2

2
5 10

1

5
1 2 3 4 5

3

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(n = 3\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc nào thêm.