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,..., 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,..., k}.

Cerința

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,...,k} și au suma cifrelor egală cu S.

Date de intrare

Fișierul de intrare numere4.in conține 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

Fișierul de ieșire numere4.out va conține 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 ≤ T ≤ 10
• 2 ≤ k ≤ 5
• 1 ≤ S ≤ 230

Exemplu:

numere4.in

2 3
3 5

numere4.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. Ultima cifră lui 4 este 4.

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. Ultima cifră a lui 13 este 3.