Однажды воспитательница детского сада повела детей в парк играть в «испорченный телефон». У каждого из $N$ детей есть один и тот же набор из $M$ слов, которые мы обозначим числами от 1 до $M$. Игра проходит следующим образом: воспитательница выстраивает детей в ряд и шепчет первому ребенку слово под номером 1. После этого первый ребенок шепчет второму ребенку слово, которое он услышал, затем второй ребенок шепчет третьему то, что услышал, и так далее до последнего ребенка. В конце последний ребенок громко произносит слово, которое он услышал.

Поскольку в тот день молодые программисты беззастенчиво громко кодировали в соседнем союзе, дети не могли сосредоточиться на игре и часто слышали совсем не то слово, которое им шептали. Однако известно следующее: определенный ребенок всегда будет слышать определенное слово одинаково, то есть если ребенку $D$ прошептали слово $A$, он всегда передаст дальше (или произнесет вслух, если он последний в ряду) одно и то же слово, независимо от того, где он находится в ряду и кто именно прошептал ему слово $A$.

Чтобы развлечься, воспитательница решила провести эксперимент: она повторила эту игру $N!$ раз, по одному разу для каждого возможного порядка детей. Она заметила, что существует слово, которое ровно $K$ раз оказалось словом, произнесенным последним ребенком вслух. Ей интересно, как это возможно, и она попросила вас реконструировать такую ситуацию.

Даны числа $N$ и $K$. Определите размер словаря $M$ и слово $X$ ($1 \le X \le M$) из этого словаря, а также для каждого из $N$ детей и каждого из $M$ слов определите слово, которое этот ребенок передаст дальше, если услышит данное слово, так чтобы выбранное слово $X$ последний ребенок в ряду произносил вслух ровно в $K$ (из общего числа $N!$) порядках. Ваше решение оценивается в зависимости от размера выбранного словаря: меньший словарь приносит больше баллов.

Подробности смотрите в разделе «Бонусы».

Входные данные

В первой строке дано число подзадачи $P$ ($1 \le P \le 2$) из раздела «Бонусы», а во второй строке — количество тестовых сценариев $T$ ($1 \le T \le 10$). Сценарии независимы друг от друга, то есть речь идет о нескольких тестовых примерах в одном входном файле.

В каждой из следующих $T$ строк содержатся два целых числа $N$ и $K$ ($1 \le N \le 12$, $0 \le K \le N!$), соответствующих одному тестовому сценарию.

Выходные данные

Для каждого из $T$ сценариев в первой строке выведите два числа: $M$ и $X$ ($1 \le X \le M \le 10\,000$), размер словаря и слово, которое последний ребенок произнес в $K$ играх. В следующих $N$ строках выведите по $M$ чисел: $j$-е число в $i$-й из этих строк обозначает слово, которое $i$-й ребенок передаст дальше, если ему прошептали слово $j$.

Бонусы

Тестовые примеры разделены на две подзадачи, внимательно прочитайте описание каждой. Если ваша программа неверна на любом из примеров, вы получите 0 баллов за эту подзадачу.

Подзадача 1 оценивается в 30 баллов, в ней $1 \le N \le 7$. Для этой подзадачи можно получить либо 0, либо все баллы. При условии, что ваша программа верна на всех примерах, единственным дополнительным условием является $M \le 10\,000$.

Подзадача 2 оценивается в 70 баллов, в ней $1 \le N \le 12$. Для этой подзадачи можно получить частичные баллы. Для каждого сценария каждого примера определяется количество баллов, которое набрал ваш алгоритм. Ваш алгоритм получит $70 \cdot B$ баллов, где $B$ — минимальное количество баллов по всем сценариям в подзадаче. Баллы за отдельный сценарий $B_S$ рассчитываются следующим образом:

• если $M \le N + 1$, то $B_S = 1$
• иначе, если $M \le N + 5$, то $B_S = 0.7 + 0.15 / (M - N - 1)$ (при этом $0.7 \le B_S \le 0.85$)
• иначе, если $M \le 5N$, то $B_S = 0.5 + 0.05 \cdot (5 - M/N)$ (при этом $0.5 \le B_S \le 0.7$)
• иначе, если $M \le 10\,000$, то $B_S = 0.5 / (\log_{10}(M / 5N) + 1)$ (при этом $0.0 \le B_S \le 0.5$)

Примеры

Входные данные 1

1
2
3 2
2 1

Выходные данные 1

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

Примечание 1

Пояснение к первому примеру: в первой игре, если порядок детей $(1, 2, 3)$, произойдет следующее: воспитательница шепчет первому ребенку слово 1. Он шепчет второму ребенку слово 2. Второй ребенок шепчет третьему ребенку слово 2, и тот произносит вслух слово 3. Другой подходящий порядок детей — $(3, 2, 1)$, для которого произнесены слова по порядку: 1 (воспитательница), 1 (ребенок №3), 3 (ребенок №2), 3 (ребенок №1). Для остальных четырех порядков последний ребенок произносит слово, отличное от 3.

Входные данные 2

2
2
3 3
4 0

Выходные данные 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

Примечание 2

Пояснение ко второму примеру: это пример из второй подзадачи, которая имеет частичное оценивание. Для первого сценария выполняется $N + 1 < M \le N + 5$, поэтому этот результат дает $0.77$ (округлено до двух десятичных знаков). Для второго сценария выполняется $M \le N + 1$, поэтому этот результат дает $1$. Поскольку берется минимум по всем тестовым сценариям, это решение получило бы $0.77$ от общего количества баллов за этот пример.