P12397 「FAOI-R9」函数大师

作为一名电脑技术大神，明月喜欢用几何画板画出各种奇形怪状函数的图象，例如 $ y=\frac{x^x}{\sin x} $，$ y=\lfloor x^{\tan x} \rfloor $，$ y=\frac{x+x^3+x^5+x^7}{1+x^2+x^4+x^6} $，它们有的连续，有的离散，有的长得很奇怪，但是作为一名中考数学 99/100 的 math master，他自信自己能掌握很多函数的规律。 于是，清风给了他一个这样的函数。

清风定义函数 $ 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 $ 两个函数图象的公共点个数，可以证明这个数值一定是有限的。

无

无

**【样例 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）：无特殊限制。