#1522. 「FAOI-R9」函数大师

「FAOI-R9」函数大师

题目描述

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

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

清风又定义 Sk(x)(x∈N∗,k∈N) S_k(x) (x\in \mathbb {N^*},k\in \mathbb{N}) ,满足:

S0(x)=x,Sk(x)=s(Sk−1(x))S_0(x) = x,S_k(x) = s(S_{k-1}(x))

清风再定义 fk(x)(x∈N∗,k∈N) f_k(x)(x\in \mathbb {N^*},k\in \mathbb{N}) ,满足:

fk(x)=∑i=0kSi(x)f_k(x)=\sum_{i=0}^{k}S_i(x)

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

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

输入格式

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

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

输出格式

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

样例

4 3
21
20
19
50
1
1
0
1

题目来源:洛谷 P12397