Mahmut is a weird dude who likes to play with numbers in a never ending cycle. Şehmettin being a entrepreneur decided to use the weirdness of Mahmut and gave him a job. Şehmettin gave him a list of N numbers and asked Mahmut to find the number of pairs that when concatenated give a number which is divisible by K. Mahmut being the weird dude he is, decided that he never cared about money and did everything for fun and started counting. After months of counting he found the result.

Feeling this was slow (which it is) Şehmettin decided to hire Zeyna (you) a quite good mathematician to create an algorithm that gets the results much faster. Help Şehmettin find the number of pairs in an efficient way.

• \(P_{i,j}\) and \(P_{j,i}\) are considered different pairs. (Assume that the ith element is 111, and the jth element is 2. Then \(P_{i,j}\) would be 1112, and \(P_{j,i}\) would be 2111.)
• \(P_{i,j}\) where \(i = j\) is not counted as a pair since it uses the element twice.

Input

• The first line contains 2 positive integers:
  • \(2 \leq N \leq 10^5\) (number of elements)
  • \(2 \leq K \leq 1000\) (number divisor)
• The second line contains N positive integers:
  • \(1 \leq a_i \leq 10^{15}\) (elements to be concatenated)

Output

Print the number of pairs.

Example

Input 1:

4 9
11 7 2 8

Output 1:

4

Input 2:

7 7
1 2 3 4 5 6 7

Output 2:

6

Explanation

Input 1: There are 4 pairs that are divisible by 9 which are:

11, 7 -> 117
7, 2 -> 72
2, 7 -> 27
7, 11 -> 711