Dans

Tot tărâmul numericesc a fost invitat la balul din Numeradonia. Fiecare numerian (reprezentat printr-un număr natural nenul) a venit în sala de bal și încearcă să-și găsească perechea. Regula după care un numerian $x$ îl poate invita la dans pe un alt numerian $y$ este în funcție de dans:

• Valsul prim: numerianul $x$ îl poate invita la dans pe numerianul $y$ dacă $x+y$ este număr prim.
• Salsa fracțional: numerianul $x$ îl poate invita la dans pe numerianul $y$ dacă mulțimea cifrelor din $y$ este inclusă în mulțimea cifrelor din $x$ (fiecare cifră care apare în $y$ apare și în $x$, cel puțin o dată; multiplicitatea nu contează).

Cifrimina își dorește să știe câți parteneri de dans ar putea găsi, în funcție de cerință.

Cerință

Se citește numărul natural $C$ (numărul cerinței), numărul natural $n$, valoarea $D$ a Cifriminei și apoi un șir de $n$ numere naturale nenule $a_1, a_2, \dots, a_n$ (numerienii din sală).

1. Dacă $C=1$, determinați pe câți numerieni îi poate invita Cifrimina la valsul prim (adică numărul de valori $a_i$ pentru care $D + a_i$ este prim).
2. Dacă $C=2$, determinați pe câți numerieni îi poate invita Cifrimina la salsa fracțional (adică numărul de valori $a_i$ ale căror cifre apar toate în $D$).

Observație: fiecare numerian este considerat distinct prin poziția sa în șir (dacă aceeași valoare apare de mai multe ori, fiecare apariție contează separat).

Date de intrare

Fișierul de intrare dans.in conține:

• pe prima linie: $C$, $n$, $D$;
• pe a doua linie: $n$ numere naturale nenule $a_1, a_2, a_3, \dots, a_n$ separate prin spațiu.

Date de ieșire

Fișierul de ieșire dans.out va conține:

• Dacă $C=1$, atunci pe prima linie a fișierului de ieșire dans.out se va scrie un număr natural reprezentând numărul de numerieni din șir pe care îi poate invita Cifrimina la valsul prim, adică numărul de valori $a_i$ pentru care $D + a_i$ este număr prim.
• Dacă $C=2$, atunci pe prima linie a fișierului de ieșire dans.out se va scrie un număr natural reprezentând numărul de numerieni din șir pe care îi poate invita Cifrimina la salsa fracțional, adică numărul de valori $a_i$ ale căror cifre apar toate în numărul $D$ (multiplicitatea cifrelor nu contează).

Restricții și precizări

• $1 \leq n \leq 10^6$
• $0 \leq D \leq 10^6$
• $0 \leq a_i \leq 10^6$
• Pentru teste în valoare de 60 de puncte, $C=1$.
• Pentru teste în valoare de 40 de puncte, $C=1$ și $n \leq 10^3$.
• Pentru teste în valoare de 30 de puncte, $C=2$.

Exemplul 1

dans.in

1 6 10
1 2 3 4 7 10

dans.out

3

Explicație

Verificăm sumele cu $D=10$:

• $10+1=11$ (prim);
• $10+2=12$;
• $10+3=13$ (prim);
• $10+4=14$;
• $10+7=17$ (prim);
• $10+10=20$.

Răspuns: $3$ parteneri.

Exemplul 2

dans.in

2 7 120
2001 33 5 101 12 222 900

dans.out

4

Explicație

Cifrele lui $D=120$ sunt în mulțimea $\{0,1,2\}$.

Acceptate:

• $2001$ — $\{0,1,2\}$;
• $101$ — $\{0,1\}$;
• $12$ — $\{1,2\}$;
• $222$ — $\{2\}$.

Respinse:

• $33$ — $\{3\}$;
• $5$ — $\{5\}$;
• $900$ — $\{0,9\}$.