Light

In the physics lab, $N$ light bulbs are lined up in a row, numbered from 1 to $N$. All bulbs are off at first. During class, each of the $K$ students picks an integer $d_i$ ($2 \le d_i \le N$). The student flips the state of every bulb whose number is a multiple of $d_i$. A bulb that is on turns off, and a bulb that is off turns on. After flipping, the student leaves the room.

Write a program that counts the bulbs that are still on after all students have left.

The first line contains the positive integer $N$. The second line contains the number of students $K$. The third line contains $K$ integers $d_1, d_2, \ldots, d_K$, separated by single spaces.

Print a single line containing the number of bulbs that remain on after all students have left.

• $3 \le N \le 10^{12}$
• $1 \le K \le 22$
• $1 \le d_i \le \min(N, 10^6)$
• The numbers $d_i$ are not necessarily distinct

Initially, all the bulbs are off. After the first student flips the bulbs, the 2nd, 4th, 6th, and 8th bulbs are on. After the second student flips the bulbs, the 2nd, 3rd, 4th, and 8th bulbs remain on.