Dada una matriz de $n \times m$, necesitas llenarla con 0 y 1, de tal manera que:

• No puede haber cuatro celdas consecutivas horizontales o verticales llenas con el mismo número.
• Las celdas llenas con 1 forman un área conectada. (Dos celdas son adyacentes si comparten un borde. Se dice que un grupo de celdas está conectado si para cada par de celdas es posible encontrar un camino que conecte las dos celdas que se encuentre completamente dentro del grupo, y que solo se desplace de una celda a una adyacente en cada paso).

Por favor, construye una matriz que satisfaga las condiciones anteriores y que tenga la mayor cantidad posible de 1s. Imprime el número máximo de 1s y la matriz.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^3$) – el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene dos enteros $n, m$ ($2 \le n, m \le 10^3$).

Se garantiza que la suma de $n \cdot m$ sobre todos los casos de prueba no excede $10^6$.

Salida

Para cada caso de prueba, imprime el número máximo de 1s en la primera línea. Luego, imprime la matriz en las siguientes $n$ líneas. Si hay múltiples soluciones, imprime cualquiera.

Ejemplos

Entrada 1

3
2 2
3 4
3 8

Salida 1

4
11
11
9
1110
1110
1110
18
11101110
10111011
11011011