D. Склеенные множители
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел.

Назовем конкатенацией чисел $$$x$$$ и $$$y$$$ такое число, что оно получается при записывании чисел $$$x$$$ и $$$y$$$ подряд без изменения порядка. Например, конкатенация чисел $$$12$$$ и $$$3456$$$ — это число $$$123456$$$.

Посчитайте количество упорядоченных пар позиций $$$(i, j)$$$ ($$$i \neq j$$$) в массиве $$$a$$$ таких, что конкатенация $$$a_i$$$ и $$$a_j$$$ делится на $$$k$$$.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

Выведите одно целое число — количество упорядоченных пар позиций $$$(i, j)$$$ ($$$i \neq j$$$) в массиве $$$a$$$ таких, что конкатенация $$$a_i$$$ и $$$a_j$$$ делится на $$$k$$$.

Примеры
Входные данные
6 11
45 1 10 12 11 7
Выходные данные
7
Входные данные
4 2
2 78 4 10
Выходные данные
12
Входные данные
5 2
3 7 19 3 3
Выходные данные
0
Примечание

В первом примере пары $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 1)$$$, $$$(3, 4)$$$, $$$(4, 2)$$$, $$$(4, 3)$$$ подходят. Они образуют числа $$$451$$$, $$$4510$$$, $$$110$$$, $$$1045$$$, $$$1012$$$, $$$121$$$, $$$1210$$$, соответственно, каждое из них делится на $$$11$$$.

Во втором примере все $$$n(n - 1)$$$ пар подходят.

В третьем примере ни одна пара не подходит.