Halum and ACM Park

The newly built ACM park is getting very popular. Initially the park is empty. Each day people come in groups to visit the park. There is a special train ride inside the park. Halum is in charge of the rides. Each time he chooses some groups and put them on K trains for a ride. Trains are numbered from 1 to K from left to right. Each train has unlimited seats. Halum maintains following rules to arrange the rides:

Now you are given Q queries of two types. Queries are explained in the input section. In each query of type 1, the number of trains K is given. For each of these queries Halum wants to know how many ways train rides can be arranged. Two ways are considered different if a group is selected in one, and not in the other or any two (one in case of he is the only rider) members (from any group) ride the same train in one, and not in the other. Order of seating in the same train does not matter.

Input

Input starts with an integer T (1<=T<=5), denoting the number of test cases.
The first line of a case contains an integer Q (1<=Q<=30,000). Each of the next Q lines contains a query in one of the following form:

Output

For each case, print the case number first. Then for each query '1 K', the number of ways train rides are possible with K trains modulo 1000000007.

Sample

2
2
0 5
1 5
4
1 1
0 5
0 10
1 1

Case 1:
120
Case 2:
0
3