G. Sleepy Pandas
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You received a shipment of $$$N$$$ pandas labelled with numbers $$$x_1, x_2, \ldots, x_N$$$ from Mars ($$$N \leq 10^5$$$, $$$1 \leq x_i \leq 10^9$$$). Additionally, you have a magical zookeeper who has a favorite number $$$K$$$ ($$$K \leq 10^9$$$). The zookeeper will do the following exactly once:

  1. Pick two distinct pandas, say panda $$$i$$$ and panda $$$j$$$, and puts them to sleep.
  2. Concatenate the numbers on the labels of panda $$$i$$$ and panda $$$j$$$ to form a new number $$$y$$$.
  3. If $$$y$$$ is not divisible by $$$K$$$, then the zookeeper ships pandas $$$i$$$ and $$$j$$$ back to Mars.

Your task is to find the number of ordered pairs $$$(i, j)$$$ such that after performing the operation above, the zookeeper does not ship pandas $$$i$$$ and $$$j$$$ back to Mars.

Note: $$$i$$$ is not necessarily less than $$$j$$$. Also, the concatenation of $$$i$$$ and $$$j$$$ is different from the concatenation of $$$j$$$ and $$$i$$$.

A concatenation of numbers $$$x$$$ and $$$y$$$ is 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$$$.

Input

The first line contains an integer $$$T$$$ ($$$T \leq 100$$$), the number of test cases.

For each test case:

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq 10^9$$$) representing the number of pandas and the zookeeper's favorite number.

The second line contains $$$N$$$ space-separated integers $$$x_1, x_2, \ldots, x_N$$$ ($$$1 \leq x_i \leq 10^9$$$) representing the labels on the pandas.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1 - 5$$$ satisfy $$$N \leq 1000$$$, and the sum of $$$N$$$ over all test cases does not exceed $$$10^4$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each test case, output a single integer representing the number of ordered pairs $$$(i, j)$$$ such that after performing the operation, the zookeeper does not ship pandas $$$i$$$ and $$$j$$$ back to Mars. Output each testcase on a new line.

Example
Input
2
4 11
1 4 3 4
3 2
1 2 3
Output
2
2
Note

For the first test case, pairs $$$(2, 4)$$$ and $$$(4, 2)$$$ result in $$$y=44$$$ which is divisible by $$$11$$$.

For the second test case, pairs $$$(1, 2)$$$ and $$$(3, 2)$$$ work.

—

Problem Idea: yash belani

Problem Preparation: jay_jayjay

Occurrences: Novice 7, Advanced 4