G. Bessie and Kaprekar
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For an $$$n$$$-digit base-$$$10$$$ integer with leading zeros, define the Kaprekar mapping $$$K_n(x)$$$ as follows:

  1. Let $$$a$$$ be the integer obtained by sorting the digits of $$$x$$$ in non-decreasing order.
  2. Let $$$b$$$ be the integer obtained by sorting the digits of $$$x$$$ in non-increasing order.
  3. Then $$$K_n(x) = b - a$$$.

For example, if $$$n = 4$$$ and $$$x = 2103$$$, then its digits are $$$0,1,2,3$$$. Sorting them gives $$$a = 0123 = 123$$$ and $$$b = 3210$$$, so $$$K_4(2103) = 3210 - 123 = 3087$$$.

The Kaprekar set of $$$x$$$, denoted $$$S_n(x)$$$, is defined as follows:

  • $$$x$$$ is in $$$S_n(x)$$$.
  • If $$$a$$$ is in $$$S_n(x)$$$, then $$$K_n(a)$$$ is also in $$$S_n(x)$$$.

You are given $$$q$$$ queries. For each query value $$$y_i$$$, determine the number of integers $$$x$$$ such that $$$0 \le x \le 10^n - 1$$$ and $$$y_i \in S_n(x)$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n \le 12,\; 1 \le q \le 10^5)$$$.

The second line contains $$$q$$$ integers $$$y_1, y_2, \dots, y_q$$$ $$$(0 \le y_i \le 10^n - 1)$$$.

Output

Print $$$q$$$ lines containing the answers to the queries in order.

Examples
Input
2 5
0 9 18 54 98
Output
10
90
17
9
1
Input
3 6
0 495 594 999 321 100
Output
10
990
841
1
1
1
Note

In the first query of the first test, there are exactly $$$10$$$ values of $$$x$$$ whose Kaprekar set contains $$$0$$$, namely $$$$$$ 00, 11, 22, \dots, 99. $$$$$$

In the fourth query of the first test, there are exactly $$$9$$$ values of $$$x$$$ whose Kaprekar set contains $$$54$$$, namely $$$$$$ 6, 17, 28, 39, 54, 60, 71, 82, 93. $$$$$$

In the fifth query of the first test, $$$98$$$ is the only number which contains $$$98$$$ in its Kaprekar set.