cat2pal

Prin concatenarea a două numere naturale $A$ și $B$ se pot obține numerele naturale $AB$ și $BA$. De exemplu, dacă $A = 8$ și $B = 8$, atunci prin concatenare se poate obține numărul $88$, iar dacă $A = 7$ și $B = 17$, atunci prin concatenare se pot obține numerele $717$ și respectiv $177$.

Cerință

Scrieți un program care să rezolve următoarele două cerințe:

1. Pentru un număr natural nenul $A$ dat, să se calculeze $P1$, numărul numerelor naturale distincte $X$, unde $1 \leq X \leq 10 * A$, astfel încât $X$ concatenat cu $A$ sau $A$ concatenat cu $X$ este palindrom.
2. Date fiind numărul natural $N$ și un șir de $N$ numere naturale $v[1], v[2], \dots, v[N]$, să se calculeze $P2$, numărul de numere palindrom distincte care se pot obține prin concatenarea numerelor din perechile $(v[i], v[j])$, unde $1 \leq i \leq N$ și $1 \leq j \leq N$.

Date de intrare

Fișierul de intrare cat2pal.in conține pe prima linie numărul natural $C$, reprezentând cerința care urmează să fie rezolvată ($1$ sau $2$). Dacă $C = 1$, atunci pe linia a doua se află numărul natural $A$. Dacă $C = 2$, atunci pe linia a doua se află numărul natural $N$ și pe linia a treia se află $N$ numere naturale separate prin spațiu, reprezentând șirul $v$.

Date de ieșire

Fișierul de ieșire cat2pal.out va conține o singură linie pe care se va scrie un singur număr natural, reprezentând rezultatul pentru cerința $C$ din fișierul de intrare.

Restricții și precizări

• $1 \leq A \lt 100 \ 000 \ 000$
• $1 \leq N \leq 10 \ 000$
• $0 \leq v[i] \lt 100 \ 000$; pentru orice $i = 1 \dots N$
• Pentru cazul $C = 2$, trebuie luate în considerare și perechile $(v[i], v[i])$, adică concatenarea unui element cu el însuși.
• Pentru teste valorând $20$ de puncte: $C = 1$ și $A < 100 \ 000$
• Pentru alte teste valorând $30$ de puncte: $C = 1$ și nu există restricții suplimentare.
• Pentru teste valorând $15$ puncte: $C = 2$ și $N ≤ 1 \ 000$
• Pentru teste valorând $35$ puncte: $C = 2$ și nu există restricții suplimentare.

Exemplul 1

cat2pal.in

1 
2

cat2pal.out

3

Explicație

$C = 1$, $A = 2$, numerele $X$ care concatenate cu $A$ produc numere palindrom sunt $2$, $12$ și $20$, deci $P1 = 3$.

Exemplul 2

cat2pal.in

2
3
2 12 21

cat2pal.out

4

Explicație

$C = 2$, $N = 3$, $v = {2, 12, 21}$, numerele palindrom distincte care pot fi obținute sunt $22$, $212$, $1221$, $2112$, deci $P2 = 4$.