B. Concatenation Pairs
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

You are also given an integer $$$k$$$.

For two integers $$$x$$$ and $$$y$$$, let $$$\mathrm{concat}(x, y)$$$ be the integer formed by writing $$$x$$$ followed by $$$y$$$ in decimal representation.

For example, $$$\mathrm{concat}(120, 45) = 12045$$$.

Your task is to count the number of ordered pairs $$$(i, j)$$$ such that $$$\mathrm{concat}(a_i, a_j)$$$ is divisible by $$$k$$$.

The order of the pair matters. Also, it is allowed that $$$i = j$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — the length of the array and the required divisor.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of ordered pairs $$$(i, j)$$$ such that $$$\mathrm{concat}(a_i, a_j)$$$ is divisible by $$$k$$$.

Example
Input
3
3 3
1 2 3
2 11
1 10
4 5
5 10 2 3
Output
3
2
8