Đèn Lồng Trung Thu
Nhân dịp Tết Trung Thu, An được bố dẫn đi mua đèn lồng. Tại cửa hàng, cậu đã choáng ngợp bởi lượng đèn lồng khổng lồ và đa dạng. Cửa hàng bán tất cả \(N\) chiếc lồng đèn. Mỗi chiếc được đánh số bởi một số nguyên \(a_i\). Hai chiếc lồng đèn có cùng một phần nguyên liệu khi chúng cùng chia hết cho một số tự nhiên khác 1. An muốn chọn cho mình một chiếc lồng đèn đặc biệt nhất, "unique" nhất. Vì vậy chiếc lồng đèn cậu chọn phải không có cùng một phần nguyên liệu với bất cứ chiếc nào khác trong cửa hàng.
Hãy giúp An đếm số lồng đèn thỏa mãn yêu cầu đặc biệt và "unique" của cậu.
Dữ liệu
- Dòng đầu tiên chứa số nguyên \(N \ (1\le N \le 10^5)\);
- Dòng tiếp theo chứa \(N\) số nguyên \(a_i \ (1 < a_i \le 10^5)\).
Kết quả
- Kết quả bài toán.
Chấm điểm
- Subtask 1 (40%): \(N \le 10^3\).
- Subtask 2 (50%): \(a_i \le 10^3\).
- Subtask 3 (10%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
5
2 4 10 3 5
output
1
Ví dụ 2
input
5
6 35 11 13 37
output
5
Comments