Huy là một cậu bé rất thích vẻ đẹp của những dãy số. Cậu định nghĩa một dãy \(𝑘\) số nguyên dương \(𝑎_1,𝑎_2,…,𝑎_𝑘\) là một dãy đẹp khi mọi cặp \(𝑖,𝑗 (1 ≤ 𝑖,𝑗 ≤ 𝑘,𝑖 ≠ 𝑗)\) thỏa mãn một trong hai điều kiện sau:

• \(𝑎_𝑖\) chia hết cho \(𝑎_𝑗\);

• \(𝑎_𝑗\) chia hết cho \(𝑎_𝑖\).

Ví dụ: Với 𝑛 = 5; 𝑎 = [7,9,3,14,63], dãy \(𝑎\) không phải là dãy đẹp (với \(𝑖 = 2, 𝑗 = 4\) không thỏa mãn các điều kiện trên).

Với \(𝑛 = 3, 𝑎 = [2, 14, 42]\), dãy \(𝑎\) là dãy đẹp. Hôm nay, Huy nhận được một dãy số nguyên dương gồm \(𝑛\) phần tử \(𝑎_1,𝑎_2,…,𝑎_𝑛\). Nếu dãy trên là một dãy số không đẹp thì Huy sẽ cảm thấy khó chịu, nên cậu ấy muốn xóa một vài phần tử của dãy \(𝑎\) để nó trở thành một dãy đẹp.

Yêu cầu: Hãy giúp Huy tính toán xem số phần tử cần xóa ít nhất là bao nhiêu.

Dữ liệu:

• Dòng đầu tiên là số nguyên dương \(𝑛 (1 ≤ 𝑛 ≤ 2 × 10^5) \)

• Dòng thứ hai gồm \(𝑛\) số nguyên dương \(𝑎_1,𝑎_2,…,𝑎_𝑛 (1 ≤ 𝑎_𝑖 ≤ 2× 10^5). \)

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả:

• Số phần tử cần xóa ít nhất để dãy \(𝑎\) trở thành một dãy đẹp.

Ràng buộc:

• Subtask 1: Có 30% test tương ứng với 30% số đểm thỏa mãn: \(𝑛 ≤ 18\);

• Subtask 2: Có 30% số test tương ứng với 30% số điểm thỏa mãn: 𝑛\( ≤ 10^3\), dãy \(𝑎\) là dãy không giảm;

• Subtask 3: Có 20% số test tương ứng với 20% số điểm thỏa mãn: \(𝑛 ≤ 2.10^5\), dãy \(a\) là dãy không giảm;

• Subtask 4: Có 20% còn lại không có ràng buộc gì thêm.

Sample Input

5 
7 9 3 14 63

Sample Output

2

Sample Input

3 
2 14 42

Sample Output

0

Giải thích:

• Ở test ví dụ đầu tiên, xóa số 7 và 14 sẽ làm dãy 𝑎 trở thành dãy đẹp.

• Ở test ví dụ thứ hai, dãy 𝑎 là một dãy đẹp nên không cần xóa phần tử nào.