# [入门赛 #21] 星云 hard ver.

## 题目背景

本题与 easy ver. 的区别在于本题**有**多组测试数据。

你看，那一抹云，衬着星星，多美啊！

## 题目描述

定义星云数为位数不大于 $n$ 且各数位之和不超过 $k$ 的正整数，给定 $n,k$，求星云数的个数。

## 输入格式

**本题有多组测试数据。**

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：  
第一行输入两个整数 $n,k$。

## 输出格式

对于每组测试数据：  
输出一行一个整数，表示答案。

## 样例 #1

### 样例输入 #1

```
2
2 1
3 2
```

### 样例输出 #1

```
2
9
```

## 提示

### 数据规模与约定

对于 $50\%$ 的数据，$1 \leq n \leq 2$。  
对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$1 \leq n \leq 7$，$1 \leq k \leq 100$。