很久以前，幼兒園老師帶孩子們到公園玩傳話遊戲。共有 $N$ 個孩子，每個人都認識同一個包含 $M$ 個單字的詞彙表，我們將這些單字編號為 $1$ 到 $M$。遊戲進行方式如下：老師將孩子們排成一列，並對第一個孩子耳語單字 $1$。接著，第一個孩子將他聽到的單字耳語給第二個孩子，第二個孩子再將他聽到的單字耳語給第三個孩子，依此類推，直到最後一個孩子。最後，最後一個孩子大聲說出他聽到的單字。

由於那天年輕的資訊學家們在附近的協會裡吵鬧地編碼，孩子們無法專心玩遊戲，因此他們經常聽到與被耳語的單字完全不同的單字。但已知以下事實：特定的孩子對於特定的單字總是會以相同的方式聽錯，也就是說，如果孩子 $D$ 被耳語單字 $A$，他之後會耳語（或如果是隊伍中最後一個則大聲說出）的單字總是相同的，無論他在隊伍中的位置為何，也無論是誰對他耳語單字 $A$。

為了自娛，老師決定進行一項實驗：她將這個遊戲重複了 $N!$ 次，即針對每一種可能的孩子排列順序各進行一次。她注意到有一個單字恰好出現了 $K$ 次，作為最後一個孩子大聲說出的單字。她想知道這是如何可能的，並請求你重建這樣的情況。

給定數字 $N$ 和 $K$。請決定詞彙表的大小 $M$ 以及該詞彙表中的一個單字 $X$ ($1 \le X \le M$)，並為 $N$ 個孩子中的每一個及 $M$ 個單字中的每一個，決定該孩子在聽到給定單字時會傳遞出的單字，使得在 $N!$ 種排列順序中，最後一個孩子大聲說出所選單字 $X$ 的次數恰好為 $K$ 次。你的解法將根據所選詞彙表的大小進行評分，詞彙表越小，得分越高。詳細資訊請參閱「評分」章節。

輸入格式

第一行包含子任務編號 $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!$)，對應一個測試案例。

輸出格式

對於每個測試案例，第一行輸出兩個數字：$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

說明

第一個範例說明：在第一場遊戲中，若孩子排列順序為 $(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$ 倍。