Background

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.

Problem Description

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.

Input Format

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$.

Output Format

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

2
2 1
3 2

2
9

Hint

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