It's been a long summer's day, with the constant chirping of cicadas and the heat which never seemed to end. Finally, it has drawn to a close. The showdown has passed, the gates are open, and only a gentle breeze is left behind.

Your predecessors had taken their final bow; it's your turn to take the stage.

Sorting through some notes that were left behind, you found a curious statement named Problem 101:

Given a positive integer sequence $$$a_1,a_2,\ldots,a_n$$$, you can operate on it any number of times. In an operation, you choose three consecutive elements $$$a_i,a_{i+1},a_{i+2}$$$, and merge them into one element $$$\max(a_i+1,a_{i+1},a_{i+2}+1)$$$. Please calculate the maximum number of operations you can do without creating an element greater than $$$m$$$.

After some thought, you decided to propose the following problem, named Counting 101:

Given $$$n$$$ and $$$m$$$. For each $$$k=0,1,\ldots,\left\lfloor\frac{n-1}{2}\right\rfloor$$$, please find the number of integer sequences $$$a_1,a_2,\ldots,a_n$$$ with elements in $$$[1, m]$$$, such that when used as input for Problem 101, the answer is $$$k$$$. As the answer can be very large, please print it modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le10^3$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1\le n\le 130$$$, $$$1\le m\le 30$$$).

Output

For each test case, output $$$\left\lfloor\frac{n+1}{2}\right\rfloor$$$ numbers. The $$$i$$$-th number is the number of valid sequences such that when used as input for Problem 101, the answer is $$$i-1$$$, modulo $$$10^9+7$$$.

Note

In the first test case, there are $$$2^3=8$$$ candidate sequences. Among them, you can operate on $$$[1,2,1]$$$ and $$$[1,1,1]$$$ once; you cannot operate on the other $$$6$$$ sequences.

Counting 101

Examples