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.

Difficulty: introductory

Starter code:

Solutions:
inp = input().split()
n = int(inp[0])
k = int(inp[1])

a = input().split()
for i in range(n):
    a[i] = int(a[i])

# End of Input

bank  = {}

# Preparation
for i in range(n):
    arg = (len(str(a[i])),a[i]%k)
    #print("Detect:",arg)
    bank[arg] = bank.get(arg,0)+1

ans = 0
# Query
for i in range(n):
    ten = 1
    for j in range(1,11):
        ten*=10
        frontMod = (a[i]*ten)%k
        #print("FRONT MOD:",frontMod)
        req = (k-frontMod)%k
        #print("WANT:",req)

        got = bank.get((j,req),0)
        ans += got

# Deal with Same Index
for i in range(n):
    cur = str(a[i])
    cur = cur*2
    tst = int(cur)
    if(tst%k==0):
        ans-=1

# Print Answer
print(ans)

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 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)



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 = 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)

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]))

def main():
    n, k = list(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 list(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 list(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)


def __starting_point():
    main()

__starting_point()

def main():
    n, k = 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()

n, k = list(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 = 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 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)

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)


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
       # print(key,c,arr[i]*mul)
        if key in cnt[c]:
           # print("*",cnt[c][key])
            ans+=cnt[c][key]
        c+=1
        mul*=10
    cnt[l][ky]+=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)]  # number length 1-10, 1-indexed
    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()

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
input = sys.stdin.readline
from collections import Counter

n,k=list(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)


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:
            #print(a[i], cur, j, d[(j, (k-y)%k)])
            res += d[(j, (k-y)%k)]
            if (cur_l, cur_y) == (j, (k-y)%k):
                res -= 1
print(res)


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


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)

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)

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)