Задан массив \(a\), состоящий из \(n\) положительных целых чисел.
Назовем конкатенацией чисел \(x\) и \(y\) такое число, что оно получается при записывании чисел \(x\) и \(y\) подряд без изменения порядка. Например, конкатенация чисел \(12\) и \(3456\) — это число \(123456\).
Посчитайте количество упорядоченных пар позиций \((i, j)\) (\(i \neq j\)) в массиве \(a\) таких, что конкатенация \(a_i\) и \(a_j\) делится на \(k\).
Выходные данные
Выведите одно целое число — количество упорядоченных пар позиций \((i, j)\) (\(i \neq j\)) в массиве \(a\) таких, что конкатенация \(a_i\) и \(a_j\) делится на \(k\).
Примечание
В первом примере пары \((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)\) пар подходят.
В третьем примере ни одна пара не подходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 11
45 1 10 12 11 7
|
7
|
|
2
|
4 2
2 78 4 10
|
12
|
|
3
|
5 2
3 7 19 3 3
|
0
|