Jumping Caterpillars

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.Integer.max;
import static java.lang.Integer.min;
import static java.lang.Integer.parseInt;

/**
 * Created by bugkiller on 15/03/19.
 */
class JumpingCaterpillars {

    private static final int a[] = new int[1000000];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t, n, k;
        String s[];
        t = parseInt(br.readLine());
        while (t-- > 0) {
            s = br.readLine().split("\\s");
            n = parseInt(s[0]);
            k = parseInt(s[1]);
            s = br.readLine().split("\\s");
            for (int i = 0; i < k; i++) {
                a[i] = parseInt(s[i]);
            }
            System.out.println(countUnEaten(n, k));
        }
    }

    private static int countUnEaten(int n, int k) {
        boolean sieve[] = new boolean[n + 1];
        int count = 0;
        initSieve(sieve, n, k);
        for (int i = 1; i <= n; i++) {
            if (!sieve[i]) {
                count++;
            }
        }
        return count;
    }

    private static void initSieve(boolean[] sieve, int n, int k) {
        for (int i = 0; i < k; i++) {
            if (a[i] <= n && !sieve[a[i]]) {
                for (int j = 1; a[i] * j <= n; j++) {
                    sieve[a[i] * j] = true;
                }
            }
        }
    }
}