Дана матрица размера $n \times m$. Вам необходимо заполнить её числами 0 и 1 так, чтобы выполнялись следующие условия:

• Не может быть четырех подряд идущих по горизонтали или вертикали ячеек, заполненных одним и тем же числом.
• Ячейки, заполненные 1, образуют связную область. (Две ячейки называются соседними, если они имеют общую сторону. Группа ячеек называется связной, если для любой пары ячеек в группе можно найти путь, соединяющий их, который полностью лежит внутри группы и на каждом шаге переходит из одной ячейки в соседнюю.)

Постройте матрицу, удовлетворяющую вышеуказанным условиям и содержащую максимально возможное количество 1. Выведите максимальное количество 1 и саму матрицу.

Входные данные

Первая строка содержит целое число $T$ ($1 \le T \le 10^3$) — количество тестов.

Для каждого теста первая строка содержит два целых числа $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