一位疯狂的科学家 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$$$ 是网格 $$$A$$$ 的行总和,$$$C_j$$$ 是列总和。
- 对于网格$$$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$$$ 个字符。第 $$$i$$$ 行中的第 $$$j$$$ 个字符应等于 $$$A_{i,j}$$$。
如果有多个答案,您可以打印任何答案。
示例
输入 #1
4 2 2 3 8 1 0 4 16
输出 #1
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)$$$的最小可能值。