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 ~k~ số nguyên dương ~a_1, a_2, \dots, a_k~ là một dãy đẹp khi mọi cặp ~i, j~ ~(1 \le i, j \le k, i \ne j)~ thỏa mãn một trong hai điều kiện sau:

• ~a_i~ chia hết cho ~a_j~;

• ~a_j~ chia hết cho ~a_i~.

Ví dụ: Với ~n = 5; a = [7,9,3,14,63]~, dãy ~a~ không phải là dãy đẹp (với ~i = 2, j = 4~ không thỏa mãn các điều kiện trên). Với ~n = 3, a = [2, 14, 42]~, dãy ~a~ là dãy đẹp. Hôm nay, Huy nhận được một dãy số nguyên dương gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. 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 ~a~ để 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.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \le n \le 2 \cdot 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 2 \cdot 10^5)~.

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

Output

Ghi số phần tử cần xóa ít nhất để dãy ~a~ trở thành một dãy đẹp.

Scoring

Sample Input 1

5
7 9 3 14 63

Sample Output 1

2

Sample Input 2

3
2 14 42

Sample Output 2

0

Notes

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

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