D. Таблица-00100
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Безумный ученый Dr.Jubal придумал задачу по программированию. Попробуйте решить ее!

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

Давайте определим:

  • $$$A_{i,j}$$$ как число, стоящее в $$$i$$$-й строке и $$$j$$$-м столбце.
  • $$$R_i = A_{i,1}+A_{i,2}+...+A_{i,n}$$$ (для всех $$$1 \le i \le n$$$).
  • $$$C_j = A_{1,j}+A_{2,j}+...+A_{n,j}$$$ (для всех $$$1 \le j \le n$$$).
  • Другими словами, $$$R_i$$$ это суммы чисел в строках и $$$C_j$$$ это суммы чисел в столбцах таблицы $$$A$$$.
  • Для таблицы $$$A$$$ определим значение $$$f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$$$ (здесь для последовательности целых чисел $$$X$$$ мы определяем $$$\max(X)$$$ как максимальное число в $$$X$$$ и $$$\min(X)$$$ как минимальное число в $$$X$$$).

Найдите любую таблицу $$$A$$$, удовлетворяющую описанному условию. Среди всех таких таблиц найдите такую, для которой значение $$$f(A)$$$ минимально возможное. Среди всех таких таблиц найдите любую.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Следующие $$$t$$$ строк содержат описания набов входных данных.

Для каждого набора входных данных в единственной строке находится два целых числа $$$n$$$, $$$k$$$ $$$(1 \le n \le 300, 0 \le k \le n^2)$$$.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных сначала выведите минимальное возможное значение $$$f(A)$$$ среди всех таблиц, для которых условие выполнено.

После этого, выведите $$$n$$$ строк, каждая содержит по $$$n$$$ символов. $$$j$$$-й символ в $$$i$$$-й строке должен быть равен $$$A_{i,j}$$$.

Если есть несколько возможных решений, вы можете вывести любое.

Пример
Входные данные
4
2 2
3 8
1 0
4 16
Выходные данные
0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111
Примечание

В первом наборе входных данных сумма всех чисел таблицы равна $$$2$$$, поэтому условие выполнено. $$$R_1 = 1, R_2 = 1$$$ и $$$C_1 = 1, C_2 = 1$$$. Тогда $$$f(A) = (1-1)^2 + (1-1)^2 = 0$$$, что является минимальным возможным значением $$$f(A)$$$.

Во втором наборе входных данных сумма всех чисел таблицы равна $$$8$$$, значит условие выполнено. $$$R_1 = 3, R_2 = 3, R_3 = 2$$$ и $$$C_1 = 3, C_2 = 2, C_3 = 3$$$. Тогда $$$f(A) = (3-2)^2 + (3-2)^2 = 2$$$. Можно доказать, что это минимальное возможное значение $$$f(A)$$$.