Let denote the number of different labeled unrooted undirected trees with vertices, such that for each , the shortest path between contains no vertex with index larger than .

Now is input and you need to calculate . There are multiple test cases.

Two trees are different if and only if there exist two vertices such that there is an edge between in one tree and there is no edge between in the other one.

令  表示有多少个不同的有  个点的有标号无根无向树， 满足对于任意  ， 之间的最短路不包含任何标号大于  的点.

已知  ，求 。有多组数据。

两棵树不同，当且仅当，存在两个点  ，使得它们之间的边在一棵树中存在，而在另一棵树中不存在。

输入描述:

The input contains multiple test cases.

The first line contains the number of test cases . Description of the test cases follows.

The description of each test case consists of one line containing integers .

输入有多组数据。

第一行一个正整数  ，表示数据组数。

接下来依次输入每组数据。

对于每组数据，输入为一行两个整数 。 

输出描述:

For each test case print a line consisting of one single integer .

对于每组数据，输出一行一个整数，表示答案。

10
3 1
1 1
3 3
4 2
6 4
6 2
5 2
4 3
6 5
1000000 1000000

3
1
2
8
144
432
50
6
120
595392237