옛날 옛적에, 유치원 선생님이 아이들을 공원으로 데려가 '망가진 전화(전화 놀이)' 게임을 했습니다. $N$명의 아이들은 각각 $1$부터 $M$까지 번호가 매겨진 동일한 $M$개의 단어 집합을 알고 있습니다. 게임은 다음과 같이 진행됩니다: 선생님이 아이들을 일렬로 세우고 첫 번째 아이에게 $1$번 단어를 속삭입니다. 그 후 첫 번째 아이는 자신이 들은 단어를 두 번째 아이에게 속삭이고, 두 번째 아이는 자신이 들은 단어를 세 번째 아이에게 속삭이는 식으로 마지막 아이까지 이어집니다. 마지막으로 마지막 아이는 자신이 들은 단어를 큰 소리로 말합니다.

그날 근처 협회에서 젊은 정보학자들이 무분별하게 큰 소리로 코딩을 하고 있었기 때문에, 아이들은 게임에 집중할 수 없었고 종종 자신에게 속삭여진 단어와는 매우 다른 단어를 들었습니다. 하지만 다음 사실은 알려져 있습니다: 특정 아이는 특정 단어를 항상 같은 방식으로 듣습니다. 즉, 아이 $D$에게 단어 $A$가 속삭여지면, 그 아이는 (마지막 순서라면 큰 소리로 말하거나, 그렇지 않다면 다음 아이에게) 자신이 어디에 있든, 누가 단어 $A$를 속삭였든 상관없이 항상 같은 단어를 전달합니다.

선생님은 재미를 위해 이 게임을 $N!$번, 즉 가능한 모든 아이들의 순서에 대해 한 번씩 반복하기로 했습니다. 선생님은 마지막 아이가 큰 소리로 말한 단어 중 정확히 $K$번 등장한 단어가 있다는 것을 알아차렸습니다. 선생님은 이것이 어떻게 가능한지 궁금해하며, 여러분에게 그러한 상황을 재구성해 달라고 부탁했습니다.

$N$과 $K$가 주어집니다. 어휘집의 크기 $M$과 그 어휘집에 포함된 단어 $X$ ($1 \le X \le M$)를 결정하고, $N$명의 아이 각각과 $M$개의 단어 각각에 대해 해당 아이가 단어를 들었을 때 전달할 단어를 결정하여, 마지막 순서의 아이가 순서 중 정확히 $K$번(총 $N!$번 중) 단어 $X$를 큰 소리로 말하도록 하십시오. 여러분의 솔루션은 선택한 어휘집의 크기에 따라 점수가 매겨지며, 어휘집이 작을수록 더 높은 점수를 받습니다. 자세한 내용은 '채점' 섹션을 참조하십시오.

입력

첫 번째 줄에는 채점 섹션의 서브태스크 번호 $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$개의 정수를 출력하십시오: $i$번째 줄의 $j$번째 숫자는 $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

입력 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

참고

첫 번째 예제 설명: 첫 번째 게임에서 아이들의 순서가 $(1, 2, 3)$이라면 다음과 같은 일이 일어납니다: 선생님이 첫 번째 아이에게 단어 $1$을 속삭입니다. 그 아이는 두 번째 아이에게 단어 $2$를 속삭입니다. 두 번째 아이는 세 번째 아이에게 단어 $2$를 속삭이고, 세 번째 아이는 단어 $3$을 큰 소리로 말합니다. 또 다른 적절한 아이들의 순서는 $(3, 2, 1)$이며, 이 경우 말해진 단어는 순서대로 $1$(선생님), $1$(아이 $3$), $3$(아이 $2$), $3$(아이 $1$)입니다. 나머지 네 가지 순서에 대해서는 마지막 아이가 $3$이 아닌 다른 단어를 말합니다.

두 번째 예제 설명: 이 예제는 부분 점수가 있는 두 번째 서브태스크의 예시입니다. 첫 번째 시나리오의 경우 $N + 1 < M \le N + 5$이므로 이 결과는 $0.77$(소수점 둘째 자리 반올림)의 점수를 받습니다. 두 번째 시나리오의 경우 $M \le N + 1$이므로 이 결과는 $1$점을 받습니다. 모든 테스트 시나리오에 대해 최솟값을 취하므로, 이 솔루션은 이 예제에 대해 총점의 $0.77$배를 받게 됩니다.