[入门赛 #21] 星云 hard ver.

题目背景

本题与 easy ver. 的区别在于本题**有**多组测试数据。 你看,那一抹云,衬着星星,多美啊!

题目描述

定义星云数为位数不大于 $n$ 且各数位之和不超过 $k$ 的正整数,给定 $n,k$,求星云数的个数。

输入输出格式

输入格式


**本题有多组测试数据。** 第一行输入一个整数 $T$,表示测试数据组数。 对于每组测试数据: 第一行输入两个整数 $n,k$。

输出格式


对于每组测试数据: 输出一行一个整数,表示答案。

输入输出样例

输入样例 #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$。