Description

Qingfeng denotes a function $s(x)\;(x \in \mathbb N^*)$ as the sum of each digit of $x$ in decimal. Formally, $s(x)$ is defined as:

$$s(x) = \sum_{i=0} \left( \lfloor \frac{x}{10^i} \rfloor \bmod 10 \right).$$

Consequently, he defines $S_k(x)\;(x \in \mathbb N^*, k \in \mathbb N)$ as follows:

$$S_k(x) = \begin{cases} x, & k = 0, \\ s(S_{k-1}(x)), & k > 0. \end{cases}$$

Moreover, Qingfeng defines $f_k(x)\;(x \in \mathbb N^*, k \in \mathbb N)$ to be $\sum_{i=0}^k S_i(x)$. After giving such a function to Mingyue, who confidently inputs the formula into the Geometer's Sketchpad and is dazzled by the graphics, Mingyue decides to ask you to find out the properties of the function.

To be specific: you are given a constant integer $k$. There are multiple queries, in each of them you are given another integer $m$, and you have to find out the number of intersection points of the graphics of the functions $y = f_k(x)$ and $y = m$. It can be proven that the result is always finite under the given constraints.

Input Format

The first line contains two integers $T$ and $k$, denoting the number of queries, and the given constant, respectively.

Then $T$ lines follow. Each line contains a single integer $m$.

Output Format

For each query, output a single line containing an integer: the answer to the corresponding query.

4 3
21
20
19
50

1
1
0
1

Hint

Sample Description

For the first test case: the sets of the x - coordinates of all the intersection points corresponding to each group of data are $\{12\}$, $\{5\}$, $\varnothing$, and $\{26\}$, respectively.

Constraints

Subtasks are used in this problem.

• Subtask 1（5 pts）: $k=0$.
• Subtask 2（20 pts）: $T \le 10$, $m \le 10^5$, $k \le 10$.
• Subtask 3（25 pts）: $T \le 10$, $m \le 10^6$, $k \le 10^4$.
• Subtask 4（25 pts）: $k \le 1$.
• Subtask 5（25 pts）: No additional constraints.

For all test cases, it is guaranteed that $1\le T\le 10^5$, $0\le k\le 10^9$, $0\le m\le 10^{18}$.