numere

Irinei îi plac numerele naturale. Ea știe că orice număr natural cu cifre nenule se poate reprezenta ca un șir de cifre din mulțimea $A = \{1, 2, \dots, 9 \}$. Irina își alege o cifră $k$ şi îşi propune să afle câte numere naturale au suma cifrelor egală cu un număr dat $S$ și în același timp se reprezintă folosind doar cifre din mulţimea $\{1, 2, \dots, k \}$.

Cerinţă

Dându-se $S$ şi $k$, se cere să se determine ultima cifră a numărului de numere naturale care se reprezintă doar cu cifre din mulțimea $\{1, \dots, k \}$ și au suma cifrelor egală cu $S$.

Date de intrare

În fișierul numere.in se află scrise pe prima linie numerele naturale $T$ şi $k$, separate printr-un spaţiu, unde $T$ reprezintă numărul de teste, iar $k$ are semnificaţia din enunţ. Pe linia a doua se găsesc $T$ numere naturale, separate prin câte un spaţiu. Al $i$-lea număr de pe linia a doua reprezintă suma $S$ corespunzătoare celui de-al $i$-lea test .

Date de ieșire

În fișierul numere.out se vor scrie pe prima linie, separate prin câte un spaţiu, $T$ cifre calculate conform cerinţelor, în ordinea dată de fişierul de intrare.

Restricții și precizări

• $1 \leq T \leq 10$
• $2 \leq k \leq 5$
• $1 \leq S \leq 2^{30}$

Exemplu

numere.in

2 3
3 5 

numere.out

4 3

Explicație

Cu cifrele ${1, 2, 3}$ şi suma cifrelor egală cu $3$ putem scrie numerele $111$, $12$, $21$, $3$ deci $4$ numere.

Cu cifrele ${1, 2, 3}$ şi suma cifrelor egală cu $5$ putem scrie numerele $11111$, $1112$, $1121$, $1211$, $2111$, $122$, $212$, $221$, $113$, $131$, $311$, $23$, $32$ deci $13$ numere.