Orășel

"La jocuri video înainte, la război înapoi!" - Mircea cel Tânăr, 2026

Lui Mircea îi place să testeze jocuri aflate încă în versiunile beta. În cel pe care îl încearcă acum, el este primarul unui orășel virtual format din $N$ căsuțe dispuse una după alta într-o linie dreaptă (partea de design va fi îmbunătățită într-un alt update). De asemenea, fiecare căsuță are un anumit grad de frumusețe. Gradul de frumusețe al unei case poate fi influențat de mai mulți factori: priveliștea pe care o oferă, mărimea ei, frumusețea exteriorului etc. Acum, Mircea vrea să afle niște informații despre unele case speciale, numite de el superbe. O casă superbă are proprietatea că gradul ei de frumusețe este un număr cu suma cifrelor divizibilă cu numărul acestora. De exemplu, casele cu gradele de frumusețe $15$, $126$ și $2442$ sunt superbe ($6$ e divizibil cu $2$, $9$ e divizibil cu $3$ și $12$ e divizibil cu $4$), în timp ce cele cu gradele de frumusețe $23$ și $1423$ nu sunt.

Cerință

Mircea are nevoie de ajutorul tău. El vrea să răspundă la două tipuri de întrebări:

1. Câte case superbe sunt în orășel?
2. Care este lungimea maximă a unei zone contigue din orășel alcătuită doar din case superbe?

Date de intrare

Prima linie a fișierului de intrare orasel.in va conține două numere naturale $C$ și $N$, unde $C$ reprezintă tipul de întrebare pentru care se va calcula răspunsul, iar $N$ reprezintă numărul de căsuțe din orășel. Pe a doua linie se vor găsi $N$ numere naturale separate prin câte un spațiu, reprezentând gradele de frumusețe pentru fiecare dintre cele $N$ case.

Date de ieșire

• Dacă $C = 1$, atunci pe prima linie a fișierului de ieșire orasel.out se va găsi un număr natural, reprezentând numărul de case superbe din orășel.
• Dacă $C = 2$, atunci pe prima linie a fișierului de ieșire orasel.out se va găsi un număr natural, reprezentând lungimea maximă a unei zone care conține doar case superbe.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• Gradele de frumusețe ale caselor sunt numere naturale cuprinse în intervalul $[1, 1 \ 000 \ 000 \ 000]$;

Exemplul 1

orasel.in

1 8
23 5 147 73 1112 33 459 43

orasel.out

5

Explicație

Casele superbe sunt cele cu gradele de frumusețe $5$, $147$, $73$, $33$ și $459$.

Exemplul 2

orasel.in

2 8
23 5 147 73 1112 33 459 43

orasel.out

3

Explicație

Zona de lungime maximă alcătuită doar din case superbe consecutive conține casele cu gradele de frumusețe $5$, $147$ și $73$.