Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Paint the Numbers

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 12:01:23 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|