昔々、幼稚園の先生が子供たちを公園に連れて行き、「伝言ゲーム」をしました。$N$ 人の子供たちはそれぞれ、$1$ から $M$ までの番号が付けられた同じ $M$ 個の単語の集合を知っています。ゲームは次のように行われます。先生は子供たちを一列に並べ、最初の子供に単語 $1$ をささやきます。その後、最初の子供が聞いた単語を次の子供にささやき、2番目の子供が聞いた単語を3番目の子供にささやき、というように最後の子供まで続きます。最後に、最後の子供が聞いた単語を声に出して言います。

その日、近くの協会で若い情報科学者たちが無遠慮に大声でコーディングをしていたため、子供たちはゲームに集中できず、ささやかれた単語とは全く異なる単語を聞き取ってしまうことがよくありました。しかし、以下のことが分かっています。ある子供は特定の単語を常に同じように聞き取ります。つまり、子供 $D$ に単語 $A$ がささやかれた場合、その子供は（列の最後であれば声に出して言う場合も含め）列のどこにいても、また誰から単語 $A$ をささやかれたとしても、常に同じ単語を次にささやきます。

先生は楽しむために実験を行うことにしました。このゲームを $N!$ 回、子供たちの可能なすべての並び順に対して1回ずつ繰り返しました。すると、最後の子供が声に出した単語として、ちょうど $K$ 回現れる単語が存在することに気づきました。先生はこれがどのように可能なのかに興味を持ち、あなたにそのような状況を再現するように頼みました。

$N$ と $K$ が与えられます。語彙のサイズ $M$ とその語彙の中の単語 $X$ ($1 \le X \le M$) を決定し、さらに $N$ 人の子供それぞれについて、$M$ 個の単語のそれぞれに対して、その単語を聞いたときに次に伝えるべき単語を決定してください。ただし、選択した単語 $X$ が、すべての並び順（合計 $N!$ 通り）のうちちょうど $K$ 回、最後の子供によって声に出されるようにしてください。あなたの解答は、選択した語彙のサイズに応じて採点され、語彙が小さいほど高い点数が与えられます。詳細は「採点」のセクションを参照してください。

入力

最初の行には、採点セクションのサブタスク番号 $P$ ($1 \le P \le 2$) が与えられます。2行目にはテストケースの数 $T$ ($1 \le T \le 10$) が与えられます。各シナリオは独立しています。つまり、1つの入力ファイルに複数のテストケースが含まれています。

続く $T$ 行のそれぞれには、1つのテストケースに対応する2つの整数 $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$ をささやかれたときに次に伝える単語を表します。

採点

テストケースは2つのサブタスクに分けられています。各説明を注意深く読んでください。プログラムがいずれかのケースで不正解の場合、そのサブタスクの点数は 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$ をささやきます。2番目の子供は3番目の子供に単語 $2$ をささやき、その子供が単語 $3$ を声に出します。もう一つの対応する子供の並び順は $(3, 2, 1)$ であり、このとき声に出された単語は順に $1$（先生）、$1$（子供3）、$3$（子供2）、$3$（子供1）となります。残りの4つの並び順では、最後の子供は $3$ 以外の単語を声に出します。

2番目の例の解説：これは部分点があるサブタスク2の例です。最初のシナリオでは $N + 1 < M \le N + 5$ が成り立つため、この結果は $0.77$（小数点以下2桁に丸め）となります。2番目のシナリオでは $M \le N + 1$ が成り立つため、この結果は $1$ となります。すべてのテストシナリオにおける最小値が採用されるため、この解法はこの例に対して合計点数の $0.77$ 倍を獲得することになります。