問題文

以下の条件を全て満たす文字列 $S$ を良い文字列とします。 ここで、$S$ の $i$ 文字目を $S_{i}$、$S$ の長さを $|S|$ と表記します。

• $3\leq |S|$
• $S$ は数字からなる
• $S_{1}$ は 0 ではない
• $S_{1}\neq S_{2}$
• $S_{1}\neq S_{|S|}$
• $S_{2}\neq S_{|S|}$
• $S_{2} = S_{3} = \cdots = S_{|S| - 1}$

例えば、167, 93336, 1000000007 は良い文字列です。また、1221, 09991, 998244353 は良い文字列ではないです。

正整数 $N, K$ が与えられます。

長さ $N + 2$ 以下の良い文字列のうち辞書順で $K$ 番目に小さい文字列を $U$ としたとき、$|U|$, $U_{1}, U_{2}, U_{|U|}$ を求めてください。なお制約よりそのような文字列 $U$ が存在することが示せます。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• $1\leq T\leq 10^{5}$
• $1\leq N\leq 2\times 10^{9}$
• $1\leq K\leq 648N$
• 入力は全て整数

入力

$T$
$case_{1}$
$case_{2}$
$\ldots$
$case_{T}$

ここで、$case_{i}$ は $i$ 番目のテストケースを表し、以下の形式で与えられます。

$N$ $K$

出力

$T$ 行出力してください。

$i$ 行目には $case_{i}$ に対する答えを以下の形式で空白区切りで出力してください。

$|U|$ $U_{1}$ $U_{2}$ $U_{|U|}$

サンプル

3
10 22
167 924
924924 167167167

10 1 0 7
54 1 0 5
754715 3 5 8