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ța

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 a1, a2, …, an (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 ai pentru care D + ai 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 ai 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 a1, a2, a3, …, an separate prin spațiu.

Date de ieșire

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

• Dacă cerința 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 ai pentru care D + ai este număr prim.
• Dacă cerința 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 ai ale căror cifre apar toate în numărul D (multiplicitatea cifrelor nu contează).

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• 1 ≤ D ≤ 1.000.000,
• 0 ≤ ai ≤ 1.000.000
• Pentru teste în valoare de 60p, C = 1
• Pentru teste în valoare de 40p, C = 1 și n ≤ 1000
• Pentru teste în valoare de 30p, C = 2
• Se acordă 10 puncte pentru exemple

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 (e prim), 10 + 2 = 12 (nu e prim), 10 + 3 = 13 (prim), 10 + 4 = 14 (nu e prim),
10 + 7 = 17 (e prim), 10 + 10 = 20 (nu e prim). 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: {0,1,2}. Acceptate: 2001 (0,1,2), 101 (0,1), 12 (1,2), 222 (2).
Respinse: 33 (3), 5 (5), 900 (9).