Dãy số đẹp là dãy các số nguyên dương có số ước số của các phần tử tăng dần.

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Người ta cần xóa ít nhất các phần tử của dãy đã cho để các phần tử còn lại tạo thành một dãy số đẹp.

Yêu cầu: Xác định số lượng phần tử của dãy số đẹp thu được.

Dữ liệu vào

Đọc từ tệp văn bản DAYSODEP.INP gồm:

• Dòng đầu ghi số nguyên dương ~n~;
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~;
• Các số trên một dòng cách nhau ít nhất một dấu cách.

Kết quả

Ghi ra tệp văn bản DAYSODEP.OUT gồm một số duy nhất là số lượng các phần tử của dãy số đẹp thu được sau khi xóa.

Ví dụ

Input:

5
10 3 5 6 12

Output:

3

Giải thích: Dãy số đẹp có thể thu được: ~3\ 6\ 12~ hoặc ~5\ 6\ 12~, đều có số ước là: ~2\ 4\ 6~.

Giới hạn

• ~1 \le n \le 5 \times 10^5~
• ~1 \le a_i \le 10^9~ (~1 \le i \le n~)
• Có ~20\%~ số điểm tương ứng với ~n \le 20~ và ~1 \le a_i \le 10^3~.
• Có ~40\%~ số điểm tương ứng với ~20 < n \le 10^3~ và ~1 \le a_i \le 10^6~.
• Có ~20\%~ số điểm tương ứng với ~10^3 < n \le 5 \times 10^4~ và ~1 \le a_i \le 10^6~.
• Có ~20\%~ số điểm tương ứng với ~5 \times 10^4 < n \le 5 \times 10^5~ và ~1 \le a_i \le 10^9~.