Once upon a time, a kindergarten teacher took the children to the park to play a game of "broken telephone." Each of the $N$ children knows the same set of $M$ words, which we will label with numbers from $1$ to $M$. The game proceeds as follows: the teacher arranges the children in a sequence and whispers the word number $1$ to the first child. Then, the first child whispers the word they heard to the second child, the second child whispers the word they heard to the third child, and so on, until the last child. Finally, the last child says the word they heard out loud.

Since the young computer scientists were coding recklessly loudly in the nearby Association that day, the children could not concentrate on the game and often heard a very different word from the one whispered to them. However, the following is known: a specific child will always hear a specific word in the same way, i.e., if child $D$ is whispered word $A$, they will always whisper (or say out loud if they are the last in the sequence) the same word, regardless of where they are in the sequence or who whispered word $A$ to them.

To have some fun herself, the teacher decided to conduct an experiment: she repeated this game $N!$ times, once for every possible ordering of the children. She noticed that there is a word that appeared exactly $K$ times as the word the last child said out loud. She is curious how this is possible and has asked you to reconstruct such a situation.

You are given the numbers $N$ and $K$. Determine the vocabulary size $M$ and a word $X$ ($1 \le X \le M$) from that vocabulary, and for each of the $N$ children and each of the $M$ words, determine the word that the child will pass on if they hear a given word, such that the chosen word $X$ is said out loud by the last child in the sequence in exactly $K$ (out of a total of $N!$) orderings. Your solution is scored based on the size of the chosen vocabulary, where a smaller vocabulary earns more points. For details, see the Scoring section.

Input

The first line contains the subtask number $P$ ($1 \le P \le 2$) from the Scoring section, and the second line contains the number of test scenarios $T$ ($1 \le T \le 10$). The scenarios are independent, i.e., there are multiple test cases in one input file.

Each of the following $T$ lines contains two integers $N$ and $K$ ($1 \le N \le 12$, $0 \le K \le N!$) corresponding to one test scenario.

Output

For each of the $T$ scenarios, print two numbers on the first line: $M$ and $X$ ($1 \le X \le M \le 10\,000$), the vocabulary size and the word that the last child said out loud in $K$ games. In the next $N$ lines, print $M$ numbers each: the $j$-th number in the $i$-th of these lines denotes the word that the $i$-th child will pass on if they are whispered word $j$.

Subtasks

The test cases are divided into two subtasks; read the descriptions of each carefully. If your program is incorrect on any of the cases, you will receive 0 points for that subtask.

Subtask 1 is worth a total of 30 points and has $1 \le N \le 7$. For this subtask, it is possible to earn 0 or all points. Provided your program is correct on all cases, the only additional condition is $M \le 10\,000$.

Subtask 2 is worth a total of 70 points and has $1 \le N \le 12$. For this subtask, partial points can be earned. For each scenario of each case, the number of points your algorithm earned is determined. Your algorithm will receive $70 \cdot B$ points, where $B$ is the minimum number of points across all scenarios in the subtask. The points for an individual scenario $B_S$ are calculated as follows:

• if $M \le N + 1$, then $B_S = 1$
• otherwise, if $M \le N + 5$, then $B_S = 0.7 + 0.15 / (M - N - 1)$ (where $0.7 \le B_S \le 0.85$)
• otherwise, if $M \le 5N$, then $B_S = 0.5 + 0.05 \cdot (5 - M/N)$ (where $0.5 \le B_S \le 0.7$)
• otherwise, if $M \le 10\,000$, then $B_S = 0.5 / (\log_{10}(M / 5N) + 1)$ (where $0.0 \le B_S \le 0.5$)

Examples

Input 1

1
2
3 2
2 1

Output 1

3 3
2 1 3
3 2 2
1 3 2
2 1
1 1
2 2

Note

Explanation of the first example: In the first game, if the order of children is $(1, 2, 3)$, the following will happen: the teacher whispers word $1$ to the first child. They whisper word $2$ to the second child. The second child whispers word $2$ to the third child, and they say word $3$ out loud. The second corresponding order of children is $(3, 2, 1)$, for which the words spoken in order are $1$ (teacher), $1$ (child number $3$), $3$ (child number $2$), $3$ (child number $1$). For the remaining four orderings, the last child says a word other than $3$.

Input 2

2
2
3 3
4 0

Output 2

6 2
1 2 3 4 5 6
6 5 4 3 2 1
2 4 1 4 3 2
2 2
1 1
1 1
1 1
1 1

Note

Explanation of the second example: This is an example in the second subtask which has partial scoring. For the first scenario, $N + 1 < M \le N + 5$ holds, so this result is worth $0.77$ (rounded to two decimal places). For the second scenario, $M \le N + 1$ holds, so this result is worth $1$. Since the minimum over all test scenarios is taken, this solution would receive $0.77$ of the total points for this example.