Dany jest macierz $n \times m$, którą należy wypełnić wartościami 0 i 1 w taki sposób, aby:

• Nie mogły istnieć cztery kolejne poziome lub pionowe komórki wypełnione tą samą liczbą.
• Komórki wypełnione 1 tworzyły spójny obszar. (Dwie komórki są sąsiednie, jeśli dzielą krawędź. Zbiór komórek jest spójny, jeśli dla każdej pary komórek istnieje ścieżka łącząca te dwie komórki, która w całości znajduje się wewnątrz zbioru i w każdym kroku przechodzi tylko z jednej komórki do komórki sąsiedniej).

Skonstruuj macierz spełniającą powyższe warunki i zawierającą jak największą liczbę jedynek. Wypisz maksymalną liczbę jedynek oraz samą macierz.

Wejście

W pierwszej linii znajduje się liczba całkowita $T$ ($1 \le T \le 10^3$) – liczba zestawów danych. Dla każdego zestawu danych w pierwszej linii znajdują się dwie liczby całkowite $n, m$ ($2 \le n, m \le 10^3$). Gwarantuje się, że suma $n \cdot m$ dla wszystkich zestawów danych nie przekracza $10^6$.

Wyjście

Dla każdego zestawu danych wypisz w pierwszej linii maksymalną liczbę jedynek. Następnie wypisz macierz w kolejnych $n$ liniach. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 1

2 2

Wyjście 1

4
11
11

Wejście 2

3 4

Wyjście 2

9
1110
1110
1110

Wejście 3

3 8

Wyjście 3

18
11101110
10111011
11011011