题目描述

在这道题中，我们称两张图同构，当且仅当两张图里同一个度数的点的个数都相同。

求所有 $n$ 个点，每个点度数不超过 $k$ 的无向图按照上述判定同构，有多少张不同的图。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个整数 $n,k$。

输出格式

共 $T$ 行，每行一个整数表示对应答案对 $10^9+9$ 取模后的值。

3 
3 2 
2 3 
4 2

5 
4 
8 

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,k\leq 10^3$，$1\leq T\leq 3$。