Description

清风定义函数 $s(x)(x \in \mathbb{N^*})$ 代表 $x$ 在十进制表示下的的各位数字之和，即：

$$s(x)=\sum_{i=0}^{+\infty}(\lfloor \frac{x}{10^i} \rfloor \bmod 10)$$

清风又定义 $S_k(x) (x\in \mathbb {N^*},k\in \mathbb{N})$，满足：

$$S_0(x) = x,S_k(x) = s(S_{k-1}(x))$$

清风再定义 $f_k(x)(x\in \mathbb {N^*},k\in \mathbb{N})$，满足：

$$f_k(x)=\sum_{i=0}^{k}S_i(x)$$

清风把这个函数给了明月，明月自信满满地将函数输入几何画板后，显示的图象让他眼花缭乱。为了探究这个函数的性质，明月找到了你。

给定你 $k$，每次询问给定你 $m$，请你求出 $y=f_k(x)$ 与 $y=m$ 两个函数图象的公共点个数，可以证明这个数值一定是有限的。

Input Format

第一行两个整数 $T,k$，表示有 $T$ 组询问，$k$ 的意义见题目描述。

接下来 $T$ 行，每行一个正整数，第 $i$ 行的表示第 $i$ 次询问的 $m$。

Output Format

对于每次询问，输出公共点的个数。

4 3
21
20
19
50

1
1
0
1

Hint

【样例 1 解释】

对于样例 $1$，每组数据对应的所有公共点的 $x$ 坐标集合分别为 $\{12\}$、$\{5\}$、$\varnothing$ 和 $\{26\}$。

【数据规模与约定】

本题采用捆绑测试。

对于每个测试点，$1 \le T \le 10^5$，$0 \le k \le 10^9$，$1 \le m \le 10^{18}$。

• 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）：无特殊限制。