Culver is staying at home and is bored. Hence he mindlessly writes a string of digits on each sheet that he has. Then, he arranges the sheets in order from left to right, to form an array of sheets.

He then notices that, if he concatenates the strings on the sheets in a subarray from left to right, he can form a number, possibly with leading zeroes.

He would like to count the number of nonempty subarrays, such that after concatenating the strings on those papers in the subarray, it forms a number that is divisible by his lucky number $d$.

Note that a subarray of an array is formed by deleting the zero or more elements from the prefix and suffix of the array.

Input

The first line contains two positive integers $n$ and $d$, denoting the number of sheets and Culver's lucky number respectively.

The $i$-th of the next $n$ lines contains of a string of digits $S_i$ each.

Output

Output an integer, the number of nonempty subarrays that have concatenation divisible by $d$.

Constraints

For all test cases, $1\le n,d\le 10^5$, $1\le |S_i|\le 15$ and $S_i$ only consists of digits for $1\le i\le n$.

Subtask 1 (5 points): $d=1$.

Subtask 2 (6 points) : $n\le 15$, $|S_i|=1$.

Subtask 3 (15 points): $n\le 1000$, $d=3$.

Subtask 4 (20 points): $d=3$.

Subtask 5 (28 points): $d$ is divisible by neither $2$ nor $5$.

Subtask 6 (26 points): No additional constraints.

Note

In the following sample test case, the $3$ desired subarrays have range $[1,6],[2,6],[6,6]$, which forms the numbers $111904120117060909051026, 04120117060909051026, 1026$ respectively, all of which can be checked to be divisible by $6$.