Cho một dãy số nguyên dương gồm \(N\) phần tử. Từ dãy số đó, hãy xoá đi ít phần tử nhất để các phần tử còn lại thoả mãn tính chất sau: với mỗi hai phần tử \(x, y\) bất kì trong dãy còn lại, \(x\) chia hết cho \(y\) hoặc \(y\) chia hết cho \(x\).

Yêu cầu: Cho dãy số nguyên gồm \(N\) phần tử, đếm số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.

Input

Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu tiên chứa số nguyên dương \(N\);
• Dòng thứ hai chứa \(N\) số nguyên dương, các số cách nhau bởi dấu cách và có giá trị không vượt quá \(10^6\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất – số lượng phần tử cần xoá đi ít nhất để thoả mãn yêu cầu bài toán.

Scoring

• Subtask #1 (\(50\%\) số điểm): \(N \leq 20\);
• Subtask #2 (\(30\%\) số điểm): \(N \leq 5000\);
• Subtask #3 (\(20\%\) số điểm): \(N \leq 10^6\);

Example

5
6 16 3 2 4

2