$n \times m$ の行列を $0$ と $1$ で埋めることを考える。このとき、以下の条件を満たす必要がある。

• 水平方向または垂直方向に、同じ数字が $4$ つ連続して並ぶことはできない。
• $1$ で埋められたセルは連結領域を形成する。（2つのセルが辺を共有している場合、それらは隣接しているという。あるセルの集合が連結であるとは、その集合内の任意の2つのセルについて、集合内のセルのみを通り、各ステップで隣接するセルへ移動することでその2つのセルを結ぶ経路が存在することをいう。）

上記の条件を満たし、かつ $1$ の数が最大となるような行列を構築せよ。$1$ の最大数と、その行列を出力せよ。

入力

入力の最初の行には、テストケースの数 $T$ ($1 \le T \le 10^3$) が含まれる。 各テストケースの最初の行には、2つの整数 $n, m$ ($2 \le n, m \le 10^3$) が含まれる。 すべてのテストケースにおける $n \cdot m$ の総和は $10^6$ を超えないことが保証される。

出力

各テストケースについて、最初の行に $1$ の最大数を出力せよ。続いて、続く $n$ 行に行列を出力せよ。複数の解が存在する場合は、そのうちのいずれかを出力すればよい。

入出力例

入力 1

3
2 2
3 4
3 8

出力 1

4
11
11
9
1110
1110
1110
18
11101110
10111011
11011011