You are given an array aa, consisting of nn positive integers.

Let's call a concatenation of numbers xx and yy the number that is obtained by writing down numbers xx and yy one right after another without changing the order. For example, a concatenation of numbers 1212 and 34563456 is a number 123456123456.

Count the number of ordered pairs of positions (i,j)(i,j) (i≠ji≠j) in array aa such that the concatenation of aiai and ajaj is divisible by kk.

The first line contains two integers nn and kk (1≤n≤2⋅1051≤n≤2⋅105, 2≤k≤1092≤k≤109).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

Print a single integer — the number of ordered pairs of positions (i,j)(i,j) (i≠ji≠j) in array aa such that the concatenation of aiai and ajaj is divisible by kk.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

int N, K;

int num[maxn];

map<long long, long long> mp[15];

int main() {

    scanf("%d%d", &N, &K);

    for(int i = 1; i <= N; i ++) {

        scanf("%d", &num[i]);

        long long a = num[i];

        for(int j = 1; j <= 10; j ++) {

            a *= 10;

            a %= K;

            mp[j][a] ++;

        }

    }

    long long cnt = 0;

    for(int i = 1; i <= N; i ++) {

        int t = num[i] % K;

        int len = log10(num[i]) + 1;

        cnt += mp[len][(K - t) % K];

        long long x = 1;

        for(int j = 1; j <= len; j ++)

            x = (x * 10) % K;

        if(((num[i] * x) % K + num[i] % K) % K == 0)

            cnt --;

    }

    printf("%I64d\n", cnt);

    return 0;

}