P1708 [Beginner Contest #21] Nebula hard ver.

The difference between this problem and the easy ver. is that this problem has multiple test cases. Look, that cloud, with the stars as its backdrop, is so beautiful.

Define a “nebula number” as a positive integer whose number of digits is not greater than $n$ and whose sum of digits is not greater than $k$. Given $n$ and $k$, find how many nebula numbers there are.

**This problem has multiple test cases.** The first line contains an integer $T$, which represents the number of test cases. For each test case: The first line contains two integers $n, k$.

For each test case: Output one integer per line, which is the answer.

### Constraints For $50\%$ of the testdata, $1 \leq n \leq 2$. For $100\%$ of the testdata, $1 \leq T \leq 10^5$, $1 \leq n \leq 7$, $1 \leq k \leq 100$. Translated by ChatGPT 5