Số nguyên tố 6

Lớp \(11\) chuyên Tin có \(n\) học sinh, thầy chủ nhiệm Linh Phan muốn chọn ra một số bạn ở lại trực nhật lớp. Để thêm tính hấp dẫn và công bằng, thầy viết một đoạn code cấp cho mỗi bạn một số tự nhiên ngẫu nhiên và quy định rằng, nếu bạn nào nhận được số có tổng các ước dương của nó nhỏ hơn hai lần số đó thì phải đi trực nhật.

Một lần không may mắn, máy tính của thầy Linh Phan đã sinh ra các số mà sau khi cấp phát cho học sinh thì không có học sinh nào phải ở lại trực nhật. Rút kinh nghiệm từ lần đó, thầy đã chuẩn bị sẵn một dãy số, rồi nhờ các em đội tuyển Tin tính xem có bao nhiêu số có tổng các ước dương nhỏ hơn hai lần số đó, nếu số lượng số này đủ nhiều thì thầy sẽ lấy dãy số đó để cấp cho các bạn trong lớp.

Yêu cầu: Cho số nguyên dương \(n\) và dãy số \(a_1\), \(a_2\),..., \(a_{n -- 1}\), \(a_n\). Hãy giúp thầy Linh Phan xác định xem với dãy số này thì có bao nhiêu em học sinh phải làm nhiệm vụ trực nhật.

Input

• Dòng đầu ghi số nguyên dương \(n\), số học sinh trong lớp.

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_{n--1}\), \(a_n\).

• \(N\leq 10^6\)

• \(a_i\leq 5.10^6\)

Output

• Gồm một số duy nhất là số học sinh phải ở lại trực nhật tương ứng với dãy số input.

Example

5
3 6 9 12 9

3

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N\leq 10^3, a_i\leq 10^4\)

• Subtask \(2\) (\(15\%\) số điểm): \(N\leq 10^4, a_i\leq 5.10^6\)

• Subtask \(3\) (\(15\%\) số điểm): Không có ràng buộc gì thêm