One day, Palak challenged Rishabh with a problem to test his skills. She gave him 2 hrs. But Rishabh had a meeting to attend with someone important. Can you solve the problem on his behalf?

Given an array A of size N, find the maximum size subset such that every 2 elements are coprime.

Two numbers x and y are said to be coprime when gcd(x, y) = 1, where gcd is the greatest common divisor.

Input

There is a single integer N in first line which denotes size of array.
The second line contains N space separated integers which are the elements of the array A.

Output

Print the size of the largest subset such that every 2 elements is coprime.

Constraints

1 ≤ N ≤ 100
1 ≤ A_i ≤ 100

Example

Input:
3
1 13 26

Output:
2