You are given an array $a$, consisting of $n$ positive integers.

Let's call a concatenation of numbers $x$ and $y$ the number that is obtained by writing down numbers $x$ and $y$ one right after another without changing the order. For example, a concatenation of numbers $12$ and $3456$ is a number $123456$.

Count the number of ordered pairs of positions $(i, j)$ ($i \neq j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $2 \le k \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print a single integer — the number of ordered pairs of positions $(i, j)$ ($i \neq j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.


-----Examples-----
Input
6 11
45 1 10 12 11 7

Output
7

Input
4 2
2 78 4 10

Output
12

Input
5 2
3 7 19 3 3

Output
0



-----Note-----

In the first example pairs $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 1)$, $(3, 4)$, $(4, 2)$, $(4, 3)$ suffice. They produce numbers $451$, $4510$, $110$, $1045$, $1012$, $121$, $1210$, respectively, each of them is divisible by $11$.

In the second example all $n(n - 1)$ pairs suffice.

In the third example no pair is sufficient.

Source: codeforces | Difficulty: HARD
Tags: Mathematics

Implementation


Solutions:
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
rem = dict()
pow10 = [10 ** j for j in range(11)]
ans = 0
for ai in a:
	key = len(str(ai))
	if key not in rem:
		rem[key] = dict()
	if ai % k not in rem[key]:
		rem[key][ai % k] = 0
	rem[key][ai % k] += 1
for ai in a:
	for j in range(1, 11):
		if j in rem:
			key = -(ai * pow10[j]) % k
			if key in rem[j]:
				ans += rem[j][key]
for ai in a:
	if int(str(ai) + str(ai)) % k == 0:
		ans -= 1
print(ans)


def main():
	(n, k) = map(int, input().split())
	(aa, cn1, cn2, sz, res) = ([], {}, {}, {}, 0)
	for w in input().split():
		a = int(w)
		if a in cn1:
			cn1[a] += 1
		else:
			cn1[a] = 1
			sz[a] = len(w)
	for (a, v) in cn1.items():
		t = (sz[a], a % k)
		cn2[t] = cn2.get(t, 0) + v
	scale1 = [10 ** i + 1 for i in range(11)]
	scale2 = [1 - s for s in scale1]
	for (a, v) in cn1.items():
		for s in range(1, 11):
			x = a * scale2[s] % k
			res += cn2.get((s, x), 0) * v
		if not a * scale1[sz[a]] % k:
			res -= v
	print(res)
main()


def main():
	(n, k) = list(map(int, input().split()))
	(aa, cnt, res) = ([], {}, 0)
	scale = [10 ** i + 1 for i in range(11)]
	for w in input().split():
		(a, s) = (int(w), len(w))
		aa.append(a)
		if not a * scale[s] % k:
			res -= 1
		t = (s, a % k)
		cnt[t] = cnt.get(t, 0) + 1
	scale = [1 - i for i in scale]
	for a in aa:
		for s in range(1, 11):
			x = a * scale[s] % k
			res += cnt.get((s, x), 0)
	print(res)

def __starting_point():
	main()
__starting_point()


from math import log10
from collections import Counter
(n, k) = [int(x) for x in input().split()]
lst = [int(x) for x in input().split()]
lst2 = []
for i in range(n):
	lst2.append((lst[i] % k, len(str(lst[i]))))
dp = [[] for i in range(12)]
for j in lst2:
	dp[j[1]].append(j[0])
for i in range(12):
	if len(dp[i]) > 0:
		dp[i] = Counter(dp[i])
ans = 0
for i in lst:
	for j in range(2, 12):
		v1 = i % k * pow(10, j - 1) % k
		if (k - v1) % k in dp[j - 1]:
			ans = ans + dp[j - 1][(k - v1) % k]
for i in lst:
	if int(str(i) + str(i)) % k == 0:
		ans = ans - 1
print(ans)


rd = lambda : list(map(int, input().split()))
((n, k), a) = (rd(), rd())

def proceed(a):
	nonlocal n, k
	b = [{} for _ in range(11)]
	ans = 0
	for i in range(n - 1, 0, -1):
		cur = a[i] % k
		ln = len(str(a[i]))
		if cur not in b[ln]:
			b[ln][cur] = 0
		b[ln][cur] += 1
		for j in range(11):
			cur = (k - a[i - 1] * 10 ** j % k) % k
			ans += b[j][cur] if cur in b[j] else 0
	return ans
print(proceed(a) + proceed(a[::-1]))


from math import log
from collections import deque
(n, k) = map(int, input().split())
s = list(map(int, input().split()))
ans = 0
s.sort()
s1 = deque(s)
for j in range(11):
	d = dict()
	z = 10 ** j
	for i in s:
		y = i * z
		u = y % k
		if u in d:
			d[u] += 1
		else:
			d.update({u: 1})
	aux = 0
	for i in s1:
		y = i
		lg = int(log(i, 10)) + 1
		lg = 10 ** lg
		if lg == z:
			aux1 = y * z % k
			aux2 = y % k
			d[aux1] -= 1
			x = k - aux2
			if aux2 == 0:
				x = 0
			if x in d:
				ans += d[x]
			d[aux1] += 1
			aux += 1
		else:
			break
	for i in range(aux):
		s1.popleft()
print(ans)


inp = input().split()
n = int(inp[0])
k = int(inp[1])
a = input().split()
for i in range(n):
	a[i] = int(a[i])
bank = {}
for i in range(n):
	arg = (len(str(a[i])), a[i] % k)
	bank[arg] = bank.get(arg, 0) + 1
ans = 0
for i in range(n):
	ten = 1
	for j in range(1, 11):
		ten *= 10
		frontMod = a[i] * ten % k
		req = (k - frontMod) % k
		got = bank.get((j, req), 0)
		ans += got
for i in range(n):
	cur = str(a[i])
	cur = cur * 2
	tst = int(cur)
	if tst % k == 0:
		ans -= 1
print(ans)


try:
	while True:
		(n, k) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		dic = {}
		for idx in range(n):
			l = len(str(arr[idx]))
			r = arr[idx] % k
			dic[l, r] = dic.get((l, r), 0) + 1
		res = 0
		for i in range(n):
			for j in range(1, 11):
				cur = arr[i] * int(pow(10, j))
				cr = cur % k
				l = len(str(arr[i]))
				r = arr[i] % k
				res += dic.get((j, (k - cr) % k), 0) - ((l, r) == (j, (k - cr) % k))
		print(res)
except Exception as e:
	pass


(n, k) = list(map(int, input().split()))
a = [int(x) for x in input().split()]
rda = []
for j in range(12):
	rd = dict()
	x = pow(10, j)
	for i in range(n):
		r = a[i] * x % k
		rd[r] = rd.setdefault(r, 0) + 1
	rda.append(rd)
ans = 0
for i in range(n):
	r = a[i] % k
	ln = len(str(a[i]))
	x = pow(10, ln)
	if r == 0:
		r = k
	if k - r in rda[ln]:
		ans += rda[ln][k - r]
		if a[i] * x % k == k - r:
			ans -= 1
print(ans)


from sys import stdin
(n, k) = [int(x) for x in stdin.readline().split()]
a = [int(x) for x in stdin.readline().split()]
mod = []
c = 1
for x in range(11):
	c %= k
	mod.append(c)
	c *= 10
counts = [{} for x in range(11)]
for x in a:
	i = len(str(x))
	if x % k in counts[i]:
		counts[i][x % k] += 1
	else:
		counts[i][x % k] = 1
total = 0
for x in a:
	for y in range(11):
		base = mod[y] * x % k
		if k - base in counts[y]:
			total += counts[y][k - base]
		if base == 0:
			if 0 in counts[y]:
				total += counts[y][0]
	if int(str(x) + str(x)) % k == 0:
		total -= 1
print(total)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
d = {}
for i in range(n):
	l = len(str(a[i]))
	y = a[i] % k
	d[l, y] = d.get((l, y), 0) + 1
res = 0
for i in range(n):
	for j in range(1, 11):
		cur = a[i] * int(pow(10, j))
		cur_l = len(str(a[i]))
		cur_y = a[i] % k
		y = cur % k
		if (j, (k - y) % k) in d:
			res += d[j, (k - y) % k]
			if (cur_l, cur_y) == (j, (k - y) % k):
				res -= 1
print(res)


import sys
input = sys.stdin.readline
l = input().split()
n = int(l[0])
k = int(l[1])
tot = [dict() for i in range(11)]
l = input().split()
li = [(int(i), len(i)) for i in l]
for i in li:
	z = i[0]
	if z % k in tot[0]:
		tot[0][z % k] += 1
	else:
		tot[0][z % k] = 1
	for j in range(1, 11):
		z = z * 10
		if z % k in tot[j]:
			tot[j][z % k] += 1
		else:
			tot[j][z % k] = 1
ans = 0
for i in li:
	z = i[0]
	y = i[1]
	a = z % k
	a = k - a
	if a == k:
		a -= k
	if a in tot[y]:
		ans += tot[y][a]
for i in li:
	z = i[0]
	y = i[1]
	if (z * pow(10, y) + z) % k == 0:
		ans -= 1
print(ans)


(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
cnt = [0] * 12
for i in range(12):
	cnt[i] = {}
for i in range(n):
	t = arr[i]
	l = 0
	while t > 0:
		t = t // 10
		l += 1
	key = arr[i] % m
	if key in cnt[l]:
		cnt[l][key] += 1
	else:
		cnt[l][key] = 1
ans = 0
for i in range(n):
	t = arr[i]
	l = 0
	while t > 0:
		t = t // 10
		l += 1
	ky = arr[i] % m
	cnt[l][ky] -= 1
	mul = 10
	c = 1
	while c <= 11:
		key = (m - mul * arr[i] % m) % m
		if key in cnt[c]:
			ans += cnt[c][key]
		c += 1
		mul *= 10
	cnt[l][ky] += 1
print(ans)


import sys
from collections import defaultdict
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
(n, k) = inpl()
a = inpl()
cnt = [defaultdict(int) for _ in range(11)]
for i in range(n):
	for j in range(1, 11):
		now = a[i] * pow(10, j, k)
		now %= k
		cnt[j][now] += 1
res = 0
for x in a:
	ln = len(str(x))
	now = (k - x % k) % k
	res += cnt[ln][now]
	if x * pow(10, ln, k) % k == now:
		res -= 1
print(res)


import sys
from collections import Counter as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, k) = I()
l = I()
ar = [i % k for i in l]
ans = []
dv = cc(ar)
for i in range(1, 12):
	x = [j * 10 ** i % k for j in l]
	ans.append(cc(x))
dv = cc(ar)
an = 0
if k == 2:
	an = dv[0] * dv[1] + dv[0] * (dv[0] - 1)
else:
	for i in range(n):
		d1 = (k - ar[i]) % k
		mu = len(str(l[i]))
		an += ans[mu - 1][d1]
		if d1 == l[i] * 10 ** mu % k:
			an -= 1
print(an)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
sz = []
t = [1] * 11
cnt = dict()
for i in range(n):
	sz.append(len(str(a[i])))
	tmp = (sz[i], a[i] % k)
	if tmp in cnt:
		cnt[tmp] += 1
	else:
		cnt[tmp] = 1
t[0] = 1
for i in range(1, 11):
	t[i] = t[i - 1] * 10 % k
ans = 0
for i in range(n):
	for l in range(1, 11):
		cur = (k - a[i] * t[l]) % k
		tmp = (l, cur)
		if tmp in cnt:
			ans += cnt[tmp]
		if sz[i] == l and cur == a[i] % k:
			ans -= 1
print(ans)


(n, k) = list(map(int, input().split()))
nums = list(map(int, input().split()))
counts = [{} for _ in range(11)]
for n in nums:
	a = n
	for i in range(11):
		r = a % k
		try:
			counts[i][r] += 1
		except KeyError:
			counts[i][r] = 1
		a *= 10
res = 0
for i in nums:
	wo = str(i)
	le = len(wo)
	mimo = (k - i % k) % k
	if mimo in counts[le]:
		res += counts[le][mimo]
		if int(wo + wo) % k == 0:
			res -= 1
print(res)


import os, sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	(n, k) = map(int, input().split())
	a = input().split()
	a1 = list(map(int, a))
	dct = [Counter() for _ in range(11)]
	for i in range(n):
		dct[len(a[i])][a1[i] % k] += 1
	ans = 0
	for i in range(n):
		x = a1[i]
		for j in range(1, 11):
			x = x * 10 % k
			if x:
				ans += dct[j][k - x]
			else:
				ans += dct[j][0]
		if not a1[i] * (pow(10, len(a[i]), k) + 1) % k:
			ans -= 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	(n, k) = geti()
	a = getl()
	ans = 0
	val = [dd(int) for i in range(11)]
	for i in a:
		val[len(str(i))][i % k] += 1
	for i in a:
		length = len(str(i))
		for j in range(1, 11):
			now = (k - i * 10 ** j % k) % k
			ans += val[j][now]
			if length == j and now == i % k:
				ans -= 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
solve()


n = input()
(n, k) = n.split(' ')
arr = input()
arr = arr.split(' ')
store = {}
n = int(n)
k = int(k)
for x in arr:
	x = int(x)
	rem = x % k
	dig = 0
	while x > 0:
		dig += 1
		x //= 10
	if not dig in store:
		store[dig] = {}
		store[dig][rem] = 1
	elif not rem in store[dig]:
		store[dig][rem] = 1
	else:
		store[dig][rem] += 1
cnt = 0
for x in arr:
	x = int(x)
	rem = x % k
	dig = 0
	while x > 0:
		dig += 1
		x //= 10
	for i in range(1, 11):
		l = 10 ** i
		l = l % k
		l = (k - rem * l % k) % k
		if i in store:
			if l in store[i]:
				cnt += store[i][l]
				if l == rem and dig == i:
					cnt -= 1
print(cnt)


(n, k) = map(int, input().split())
(*a,) = map(int, input().split())
from collections import defaultdict
mods = [defaultdict(int) for i in range(10)]
for ai in a:
	for i in range(1, 11):
		mods[i - 1][ai * pow(10, i, k) % k] += 1
ans = 0
for ai in a:
	slen = len(str(ai))
	if ai % k == 0:
		ans += mods[slen - 1][0] - 1
	else:
		ans += mods[slen - 1][k - ai % k]
		if ai * pow(10, slen, k) % k == k - ai % k:
			ans -= 1
print(ans)


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
ais = list(map(int, input().split()))
TT = +10
mem = {}
for p in range(1, TT + 1):
	mem[p] = 10 ** p % k
h = {}
for i in range(1, TT + 1):
	t = mem[i]
	h[i] = collections.Counter([ai * t % k for ai in ais])
ans = 0
for ai in ais:
	ls = len(str(ai))
	v = ai * mem[ls]
	v %= k
	h[ls][v] -= 1
	p = -ai % k
	ans += h[ls][p]
	h[ls][v] += 1
print(ans)


from collections import defaultdict
from string import ascii_lowercase
from sys import stdin, stdout
input = stdin.readline

def main():
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	mod = [defaultdict(int) for i in range(11)]
	for val in a:
		mod[len(str(val))][val % k] += 1
	pairs = 0
	for val in a:
		for _len in range(1, 11):
			mod1 = val * 10 ** _len % k
			mod2 = k - mod1 if mod1 != 0 else 0
			pairs += mod[_len][mod2]
			if len(str(val)) == _len and val % k == mod2:
				pairs -= 1
	print(pairs)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
a = input().split()
mods = [dict() for i in range(10)]
l = [0] * n
for i in range(n):
	l[i] = len(a[i])
	a[i] = int(a[i]) % k
	cur = a[i]
	for j in range(10):
		cur = cur * 10 % k
		mods[j][cur] = mods[j].get(cur, 0) + 1
ans = 0
for i in range(n):
	mod = (k - a[i]) % k
	ans += mods[l[i] - 1].get(mod, 0)
	cur = a[i]
	for j in range(l[i]):
		cur = cur * 10 % k
	if cur == mod:
		ans -= 1
print(ans)


import sys
input = sys.stdin.buffer.readline
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
d = [{} for i in range(11)]
for i in range(n):
	st = arr[i]
	for j in range(11):
		r = st % k
		try:
			d[j][r] += 1
		except KeyError:
			d[j][r] = 1
		st *= 10
count_pair = 0
for i in arr:
	st = str(i)
	l = len(st)
	mod_st = (k - i % k) % k
	if mod_st in d[l]:
		count_pair += d[l][mod_st]
		if int(st + st) % k == 0:
			count_pair -= 1
print(count_pair)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = []
for i in range(11):
	c = {}
	for j in range(n):
		d = a[j] * 10 ** i % k
		if d in c.keys():
			c[d] += 1
		else:
			c[d] = 1
	b.append(c)
s = 0
for i in range(n):
	c = a[i] % k
	d = (k - c) % k
	if d in b[len(str(a[i]))]:
		s += b[len(str(a[i]))][d]
	if a[i] * 10 ** len(str(a[i])) % k == d:
		s -= 1
print(s)


def main():
	(n, k) = map(int, input().split())
	v = list(map(int, input().split()))
	d = {}
	ans = 0
	for x in v:
		(num_d, mod_k) = (len(str(x)), x % k)
		d.setdefault(num_d, {}).setdefault(mod_k, []).append(x)
	for x in v:
		(num_d, mod_k) = (len(str(x)), x % k)
		for (add, mods) in d.items():
			val_mod = mod_k * 10 ** add % k
			need_mod = (k - val_mod) % k
			ans += len(mods.get(need_mod, []))
			if need_mod == mod_k and add == num_d:
				ans -= 1
	print(ans)
main()


from collections import Counter
c = [Counter() for i in range(11)]
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [[] for i in range(11)]
for j in range(n):
	b[len(str(a[j]))].append(a[j])
	for i in range(1, 11):
		r = a[j] * 10 ** i % k
		c[i][r] += 1
s = 0
for i in range(11):
	y = b[i]
	for j in range(len(y)):
		p = y[j] % k
		if p == 0:
			p = k
		p = k - p
		r = y[j] * 10 ** i + y[j]
		if r % k == 0:
			s += c[i][p] - 1
		else:
			s += c[i][p]
print(s)


import sys
input = sys.stdin.readline
from collections import Counter
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
D = [Counter() for i in range(11)]
for a in A:
	for j in range(1, 11):
		D[j][a * 10 ** j % k] += 1
ANS = 0
for a in A:
	L = len(str(a))
	x = -a % k
	if a * 10 ** L % k == x:
		ANS -= 1
	ANS += D[L][x]
print(ANS)


rd = lambda : list(map(int, input().split()))
(n, k) = rd()
a = rd()
p = [0] * 12
sz = [0] * (n + 5)
p[0] = 1
r = [{} for _ in range(11)]
for i in range(1, 11):
	p[i] = 10 % k * p[i - 1] % k
for i in range(n):
	tmp = a[i]
	ct = len(str(a[i]))
	sz[i] = ct
	if a[i] % k not in r[ct]:
		r[ct][a[i] % k] = 1
	else:
		r[ct][a[i] % k] += 1
ans = 0
for i in range(n):
	rm = a[i] % k
	for j in range(1, 11):
		req = (k - rm * p[j] % k) % k
		if req in r[j]:
			ans += r[j][req]
		if req == rm and sz[i] == j:
			ans -= 1
print(ans)


import sys
import collections as cc
I = lambda : list(map(int, input().split()))
(n, k) = I()
l = I()
ar = [cc.defaultdict(int) for i in range(11)]
for i in range(1, 11):
	for j in l:
		temp = j * 10 ** i
		ar[i][temp % k] += 1
ans = 0
for i in l:
	now = len(str(i))
	ne = (k - i % k) % k
	ans += ar[now][ne]
	if ne == i * 10 ** now % k:
		ans -= 1
print(ans)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
table = [0] * 15
table[0] = 1
for i in range(1, 15):
	table[i] = 10 * table[i - 1]
	table[i] %= k
from collections import defaultdict
D = [defaultdict(lambda : 0) for _ in range(11)]
for a in A:
	j = len(str(a))
	D[j][a % k] += 1
ans = 0
for a in A:
	for j in range(11):
		t = -a * table[j]
		t %= k
		ans += D[j][t]
	j = len(str(a))
	if (a * table[j] + a) % k == 0:
		ans -= 1
print(ans)


def solve():
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	a_pows = []
	a_pow_dict = [{} for u in range(11)]
	for j in range(n):
		x = a[j] % k
		i = 0
		while i < 11:
			if x in a_pow_dict[i]:
				a_pow_dict[i][x] += 1
			else:
				a_pow_dict[i][x] = 1
			i += 1
			x = x * 10 % k
	c = 0
	for x in a:
		m = len(str(x))
		if -x % k in a_pow_dict[m]:
			c += a_pow_dict[m][-x % k]
			c -= int(int(str(x) * 2) % k == 0)
	return c
print(solve())


from math import log
(n, k) = map(int, input().split())
s = list(map(int, input().split()))
ans = 0
for j in range(11):
	d = dict()
	z = 10 ** j
	for i in s:
		y = i * z
		u = y % k
		if u in d:
			d[u] += 1
		else:
			d.update({u: 1})
	for i in s:
		y = i
		lg = int(log(i, 10)) + 1
		lg = 10 ** lg
		if lg == z:
			d[y * z % k] -= 1
			x = k - y % k
			if y % k == 0:
				x = 0
			if x in d:
				ans += d[x]
			d[y * z % k] += 1
print(ans)