Étant donné une matrice $n \times m$, vous devez la remplir avec des $0$ et des $1$, de telle sorte que :

• Il ne peut pas y avoir quatre cellules consécutives horizontales ou verticales remplies avec le même nombre.
• Les cellules remplies avec $1$ forment une zone connexe. (Deux cellules sont adjacentes si elles partagent une arête. Un groupe de cellules est dit connexe si, pour chaque paire de cellules, il est possible de trouver un chemin reliant les deux cellules qui se trouve entièrement à l'intérieur du groupe, et qui ne se déplace d'une cellule à une cellule adjacente qu'à chaque étape.)

Veuillez construire une matrice satisfaisant les conditions ci-dessus et contenant autant de $1$ que possible. Affichez le nombre maximum de $1$, suivi de la matrice.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^3$) – le nombre de cas de test.

Pour chaque cas de test, la première ligne contient deux entiers $n, m$ ($2 \le n, m \le 10^3$).

Il est garanti que la somme de $n \cdot m$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez le nombre maximum de $1$ sur la première ligne. Ensuite, affichez la matrice sur les $n$ lignes suivantes. S'il existe plusieurs solutions, affichez-en une quelconque.

Exemples

Entrée 1

3
2 2
3 4
3 8

Sortie 1

4
11
11
9
1110
1110
1110
18
11101110
10111011
11011011