Werewolves

There are $n$ players sitting in a row and $m$ kinds of identity cards. The players are numbered from $1 \sim n$. The number is public, which means everyone knows the number of each other.

A moderator will give each player an identity card. However, the receiver isn’t allowed to view their identity.

Everybody will shut their eyes. Then the moderator will call out each player in turn. All other players’ identity cards, disordered, will be shown to that player. The player should guess their identity and shut their eyes afterward. All other players will remain their eyes closed during the procedure.

The players have enough time to discuss before the game starts and want to make sure that at least $\lfloor \frac{n}{m} \rfloor$ of the guesses are correct. Please help them make a strategy.

Input

The first line contains an integer $T$, denoting the number of testcases.

Each testcase contains two integers $n,m$, separated by a space.

The input guarantees that $2 \leq m \leq n,m^n \leq 2.1 \times 10^6, \sum m^n \leq 1.4 \times 10^7$.

Output

For each testcase, output $n$ lines, line $p$ denoting the strategy of player $p$.

Denote a sequence $s$ valid if and only if $s$ is a non-descending sequence of length $n − 1$ and contains integers in $[1,m]$. Denote the count of valid sequence $c$, then output $c$ integers between $1$ and $m$, the $k$-th integer representing what the player will guess when the multiset of identity cards seen is equal to the multiset of the $k$-th valid sequence sorted in lexicographical order.

Example

1
2 2

1 2
2 1