Intersecting Graphs of the Sum-of-Digits Function

Let \( s(x) \) for \( x\in \mathbb{N^*} \) denote the sum of the digits of \( x \) in its decimal representation, i.e.,

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

Define \( S_k(x) \) for \( x\in \mathbb{N^*} \) and \( k\in \mathbb{N} \) as follows:

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

Also, define

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

Given a fixed non-negative integer \( k \) and a query number \( m \), determine the number of intersection points between the graphs of \( y=f_k(x) \) and \( y=m \) (i.e. the number of positive integers \( x \) satisfying \( f_k(x)=m \)). It can be proven that this number is finite.

inputFormat

The first line contains two integers: \( k \) (with \( k\ge 0 \)) and \( q \) (the number of queries).

Each of the following \( q \) lines contains one integer \( m \) (with \( m\ge 1 \)).

outputFormat

For each query, output a single integer on its own line representing the number of positive integers \( x \) such that \( f_k(x)=m \).

sample

0 3
1
2
10

1
1
1