Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

* For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

* All values in input are integers.
* 1 \leq N \leq 2 \times 10^5
* 1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_N


Output

Print the answer.

Examples

Input

5
24 11 8 3 16


Output

3


Input

4
5 5 5 5


Output

0


Input

10
33 18 45 28 8 19 89 86 2 4


Output

5
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        HashMap<Integer, Integer> map = new HashMap<>();
        int[] a = new int[n];

        for(int i = 0; i < n; i++){
            int ai = sc.nextInt();
            a[i] = ai;
            if(map.containsKey(ai)){
                map.put(ai, map.get(ai) + 1);
            }else{
                map.put(ai, 1);
            }
        }

        int ans = 0;

        next:
        for(int i = 0; i < n; i++){
            List<Integer> prime = divisor(a[i]);
            if(map.get(a[i]) > 1){
                continue next;
            }
            for(Integer l : prime){
                if(map.containsKey(l) && l != a[i]){
                    continue next;
                }
            }
            ans++;
        }

        System.out.println(ans);

    }

    static List<Integer> divisor(int n){
        List<Integer> result = new ArrayList<>();
        List<Integer> reverse = new ArrayList<>();
        int i = 0;
        long sqrt = (long)Math.ceil(Math.sqrt(n));
        while(++i < sqrt){
            if(n % i == 0){
                result.add(i);
                reverse.add(n / i);
            }
        }
        if(i * i == n){
            result.add(i);
        }
        Collections.reverse(reverse);
        result.addAll(reverse);
        return result;
    }

}
