Érase una vez, una maestra de jardín de infantes llevó a los niños al parque para jugar al teléfono descompuesto. Cada uno de los $N$ niños conoce el mismo conjunto de $M$ palabras, las cuales denotaremos con números del 1 al $M$. El juego se desarrolla de la siguiente manera: la maestra ordena a los niños en una fila y le susurra al primer niño la palabra número 1. Después de eso, el primer niño le susurra la palabra que escuchó al segundo niño, luego el segundo niño le susurra la palabra que escuchó al tercero, y así sucesivamente hasta el último niño. Entonces, el último niño dice en voz alta la palabra que escuchó.

Dado que ese día los jóvenes informáticos estaban programando ruidosamente en el centro cercano, los niños no pudieron concentrarse en el juego y a menudo escucharon una palabra muy diferente a la que se les susurró. Sin embargo, se sabe lo siguiente: un niño determinado siempre escuchará una palabra determinada de la misma manera, es decir, si al niño $D$ se le susurra la palabra $A$, él siempre susurrará (o dirá en voz alta si es el último de la fila) la misma palabra, sin importar dónde se encuentre en la fila o quién le haya susurrado la palabra $A$.

Para divertirse también, la maestra decidió realizar un experimento: repitió este juego $N!$ veces, una vez por cada posible orden de los niños. Notó que existe una palabra que apareció exactamente $K$ veces como la palabra que el último niño dijo en voz alta. Le interesa saber cómo es esto posible y le ha pedido que reconstruya dicha situación.

Se dan los números $N$ y $K$. Determine el tamaño del vocabulario $M$ y una palabra $X$ ($1 \le X \le M$) de ese vocabulario, y para cada uno de los $N$ niños y cada una de las $M$ palabras, determine la palabra que ese niño transmitirá si escucha una palabra dada, de modo que el último niño en el orden diga en voz alta la palabra elegida $X$ en exactamente $K$ (de un total de $N!$) órdenes. Su solución se califica dependiendo del tamaño del vocabulario elegido, donde un vocabulario más pequeño otorga más puntos. Para más detalles, consulte la sección de Subtareas.

Entrada

En la primera línea se da el número de subtarea $P$ ($1 \le P \le 2$) de la sección de Subtareas, y en la segunda línea el número de escenarios de prueba $T$ ($1 \le T \le 10$). Los escenarios son independientes entre sí, es decir, se trata de varios casos de prueba en un solo archivo de entrada.

En cada una de las siguientes $T$ líneas hay dos números enteros $N$ y $K$ ($1 \le N \le 12$, $0 \le K \le N!$) que corresponden a un escenario de prueba.

Salida

Para cada uno de los $T$ escenarios, imprima en la primera línea dos números: $M$ y $X$ ($1 \le X \le M \le 10\,000$), el tamaño del vocabulario y la palabra que el último niño dijo en voz alta en $K$ juegos. En las siguientes $N$ líneas, imprima $M$ números cada una: el $j$-ésimo número en la $i$-ésima de esas líneas indica la palabra que el $i$-ésimo niño transmitirá si se le susurra la palabra $j$.

Subtareas

Los casos de prueba están divididos en dos subtareas; lea cuidadosamente las descripciones de cada una. Si su programa es incorrecto en cualquiera de los casos, obtendrá 0 puntos para esa subtarea.

La Subtarea 1 tiene un valor total de 30 puntos y en ella se cumple $1 \le N \le 7$. Para esta subtarea es posible obtener 0 o todos los puntos. Con la condición de que su programa sea correcto en todos los casos, la única condición adicional es $M \le 10\,000$.

La Subtarea 2 tiene un valor total de 70 puntos y en ella se cumple $1 \le N \le 12$. Para esta subtarea es posible obtener puntos parciales. Para cada escenario de cada caso, se determina el número de puntos que su algoritmo ha ganado. Su algoritmo obtendrá $70 \cdot B$ puntos, donde $B$ es el número mínimo de puntos en todos los escenarios de la subtarea. Los puntos para un escenario individual $B_S$ se calculan de la siguiente manera:

• si $M \le N + 1$, entonces $B_S = 1$
• de lo contrario, si $M \le N + 5$, entonces $B_S = 0.7 + 0.15 / (M - N - 1)$ (se cumple $0.7 \le B_S \le 0.85$)
• de lo contrario, si $M \le 5N$, entonces $B_S = 0.5 + 0.05 \cdot (5 - M/N)$ (se cumple $0.5 \le B_S \le 0.7$)
• de lo contrario, si $M \le 10\,000$, entonces $B_S = 0.5 / (\log_{10}(M / 5N) + 1)$ (se cumple $0.0 \le B_S \le 0.5$)

Ejemplos

Entrada 1

1
2
3 2
2 1

Salida 1

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

Nota

Explicación del primer ejemplo: en el primer juego, si el orden de los niños es (1, 2, 3), sucederá lo siguiente: la maestra le susurra al primer niño la palabra 1. Él le susurra al segundo niño la palabra 2. El segundo niño le susurra al tercer niño la palabra 2 y este dice en voz alta la palabra 3. El otro orden de niños correspondiente es (3, 2, 1), para el cual las palabras dichas son, en orden, 1 (maestra), 1 (niño número 3), 3 (niño número 2), 3 (niño número 1). Para los cuatro órdenes restantes, el último niño dice una palabra diferente de 3.

Entrada 2

2
2
3 3
4 0

Salida 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

Nota

Explicación del segundo ejemplo: este es un ejemplo de la segunda subtarea que tiene calificación parcial. Para el primer escenario se cumple $N + 1 < M \le N + 5$, por lo que este resultado vale 0.77 (redondeado a dos decimales). Para el segundo escenario se cumple $M \le N + 1$, por lo que este resultado vale 1. Dado que se toma el mínimo de todos los escenarios de prueba, esta solución obtendría 0.77 del número total de puntos para este ejemplo.