solution

Bối cảnh

Phép thử Fermat kiểm tra "$n$ có thể là số nguyên tố hay không" bằng cách chọn một cơ số $a$ ($1 < a < n$, $\gcd(a,n)=1$) và kiểm tra:

$a^{n-1} \equiv 1 \pmod n.$

Nếu điều này sai với một cơ số $a$ nào đó, chắc chắn $n$ là hợp số ($a$ là "nhân chứng" — witness). Tuy nhiên nếu điều này đúng, $n$ chưa chắc là số nguyên tố — $a$ khi đó được gọi là một kẻ nói dối Fermat (Fermat liar). Đặc biệt, tồn tại các hợp số gọi là số Carmichael (ví dụ $561 = 3 \times 11 \times 17$) mà mọi cơ số $a$ nguyên tố cùng nhau với $n$ đều là kẻ nói dối — phép thử Fermat hoàn toàn bị đánh lừa với các số này, đó là lý do các hệ thống mật mã hiện đại dùng Miller-Rabin thay vì Fermat thuần túy.

Đề bài

Cho một số nguyên $n$ và danh sách $k$ cơ số $a_1, \ldots, a_k$ (với $1 < a_i < n$). Với mỗi cơ số $a_i$ thỏa $\gcd(a_i, n) = 1$, kiểm tra xem $a_i^{n-1} \bmod n$ có bằng $1$ hay không (tức $a_i$ có phải kẻ nói dối Fermat đối với $n$ hay không — bất kể $n$ thực sự nguyên tố hay hợp số). Các cơ số $a_i$ có $\gcd(a_i, n) \neq 1$ bị loại, không tính vào kết quả.

In ra số lượng cơ số $a_i$ (trong số các cơ số hợp lệ, tức nguyên tố cùng nhau với $n$) thỏa mãn $a_i^{n-1} \equiv 1 \pmod n$.

Ràng buộc

• $3 \le n \le 10^6$.
• $1 \le k \le 20$.
• $1 < a_i < n$ với mọi $i$.

Ví dụ

Input:

561 6
2 5 7 13 17 19

Output:

5

Giải thích: $561 = 3 \times 11 \times 17$ là số Carmichael. Trong 6 cơ số, cơ số $17$ có $\gcd(17,561)=17 \neq 1$ nên bị loại; 5 cơ số còn lại ($2,5,7,13,19$) đều nguyên tố cùng nhau với $561$ và đều thỏa $a^{560} \equiv 1 \pmod{561}$ (tức đều là kẻ nói dối Fermat) — minh họa đúng tính chất của số Carmichael.