Prieteni5

Cerință

Se consideră un șir de $n$ numere naturale nenule.

Pentru un număr natural $x$, numim divizor prietenos al lui $x$ orice divizor pozitiv $d$ al lui $x$ care îndeplinește simultan următoarele condiții:

1. suma cifrelor lui $d$ este un număr natural nenul;
2. această sumă divide pe $x$.

Indicele de prietenie al lui $x$ reprezintă numărul total de divizori prietenoși ai lui $x$.

Pentru fiecare dintre cele $n$ numere naturale date, se calculează indicele de prietenie. Cunoscând cerința $c$, numărul $n$ de numere și numerele din șir, se cere:

1. Să se determine câte numere au indicele de prietenie număr impar.
2. Să se afișeze cel mai mare număr de maxim $3$ cifre care poate fi format cu cifre ale indicilor de prietenie ale tuturor numerelor din șir.

Date de intrare

Fișierul de intrare prieteni.in conține pe prima linie numărul natural $c$ al cerinței, care poate fi doar $1$ sau $2$, pe a doua linie numărul natural nenul $n$ și apoi $n$ numere naturale nenule, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire prieteni.out va conține, pe prima linie, valoarea determinată conform cerinței.

Restricții și precizări

• $2 \leq n \leq 1 \ 000 \ 000$;
• Fiecare număr din șir este un număr natural nenul $\leq 100 \ 000$;
• Se garantează că există cel puțin un număr în șir;
• Pentru cerința $1$, se acordă $32$ de puncte;
• Pentru cerința $2$, se acordă $68$ de puncte.

Exemplul 1

prieteni.in

1
5
56 36 42 30 48

prieteni.out

4

Explicație

Şirul conține $5$ numere: $56$, $36$, $42$, $30$, $48$. Indicii de prietenie sunt: $56→5$, $36→9$, $42→7$, $30→8$, $48→9$.

Cerința este $1$, deci există $4$ numere cu indicele de prietenie impar.

Exemplul 2

prieteni.in

2
5
56 36 42 30 48

prieteni.out

998

Explicație

Şirul conține $5$ numere: $56$, $36$, $42$, $30$, $48$. Indicii de prietenie sunt: $56→5$, $36→9$, $42→7$, $30→8$, $48→9$.

Cerința este $2$, cel mai mare număr de maxim $3$ cifre care se poate forma cu cifrele $5$, $9$, $7$, $8$, $9$ este $998$.