Paint the Numbers

You are given a sequence of integers $a_1, a_2, \dots, a_n$. You need to paint elements in colors, so that:

• If we consider any color, all elements of this color must be divisible by the minimal element of this color.
• The number of used colors must be minimized.

For example, it’s fine to paint elements $[40, 10, 60]$ in a single color, because they are all divisible by $10$. You can use any color an arbitrary amount of times (in particular, it is allowed to use a color only once). The elements painted in one color do not need to be consecutive.

For example, if $a=[6, 2, 3, 4, 12]$ then two colors are required: let’s paint $6$, $3$ and $12$ in the first color ($6$, $3$ and $12$ are divisible by $3$) and paint $2$ and $4$ in the second color ($2$ and $4$ are divisible by $2$). For example, if $a=[10, 7, 15]$ then $3$ colors are required (we can simply paint each element in an unique color).

Input

The first line contains an integer $n$ ($1 \le n \le 100$), where $n$ is the length of the given sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$). These numbers can contain duplicates.

Output

Print the minimal number of colors to paint all the given numbers in a valid way.

Examples

input

6
10 2 3 5 4 2

output

3

input

4
100 100 100 100

output

1

input

8
7 6 5 4 3 2 2 3

output

4

Note

In the first example, one possible way to paint the elements in $3$ colors is:

• paint in the first color the elements: $a_1=10$ and $a_4=5$,
• paint in the second color the element $a_3=3$,
• paint in the third color the elements: $a_2=2$, $a_5=4$ and $a_6=2$.

In the second example, you can use one color to paint all the elements.

In the third example, one possible way to paint the elements in $4$ colors is:

• paint in the first color the elements: $a_4=4$, $a_6=2$ and $a_7=2$,
• paint in the second color the elements: $a_2=6$, $a_5=3$ and $a_8=3$,
• paint in the third color the element $a_3=5$,
• paint in the fourth color the element $a_1=7$.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0; i < n; i++) {
    int ok = 0;
    for (int j = 0; j < i; j++) {
      if (a[i] % a[j] == 0) {
        ok = 1;
        break;
      }
    }
    if (!ok) {
      ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}