A mad scientist Dr.Jubal has made a competitive programming task. Try to solve it!

You are given integers $n,k$. Construct a grid $A$ with size $n \times n$ consisting of integers $0$ and $1$. The very important condition should be satisfied: the sum of all elements in the grid is exactly $k$. In other words, the number of $1$ in the grid is equal to $k$.

Let's define:  $A_{i,j}$ as the integer in the $i$-th row and the $j$-th column.  $R_i = A_{i,1}+A_{i,2}+...+A_{i,n}$ (for all $1 \le i \le n$).  $C_j = A_{1,j}+A_{2,j}+...+A_{n,j}$ (for all $1 \le j \le n$).  In other words, $R_i$ are row sums and $C_j$ are column sums of the grid $A$.  For the grid $A$ let's define the value $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ (here for an integer sequence $X$ we define $\max(X)$ as the maximum value in $X$ and $\min(X)$ as the minimum value in $X$). 

Find any grid $A$, which satisfies the following condition. Among such grids find any, for which the value $f(A)$ is the minimum possible. Among such tables, you can find any.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case the only line contains two integers $n$, $k$ $(1 \le n \le 300, 0 \le k \le n^2)$.

It is guaranteed that the sum of $n^2$ for all test cases does not exceed $10^5$.


-----Output-----

For each test case, firstly print the minimum possible value of $f(A)$ among all tables, for which the condition is satisfied.

After that, print $n$ lines contain $n$ characters each. The $j$-th character in the $i$-th line should be equal to $A_{i,j}$.

If there are multiple answers you can print any.


-----Example-----
Input
4
2 2
3 8
1 0
4 16

Output
0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111



-----Note-----

In the first test case, the sum of all elements in the grid is equal to $2$, so the condition is satisfied. $R_1 = 1, R_2 = 1$ and $C_1 = 1, C_2 = 1$. Then, $f(A) = (1-1)^2 + (1-1)^2 = 0$, which is the minimum possible value of $f(A)$.

In the second test case, the sum of all elements in the grid is equal to $8$, so the condition is satisfied. $R_1 = 3, R_2 = 3, R_3 = 2$ and $C_1 = 3, C_2 = 2, C_3 = 3$. Then, $f(A) = (3-2)^2 + (3-2)^2 = 2$. It can be proven, that it is the minimum possible value of $f(A)$.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n, k = map(int, input().split())
    mat = [[0] * n for _ in range(n)]
    for i in range(n):
        b = False
        for j in range(n):
            if i*n+j == k:
                b = True
                break
            mat[(i+j)%n][j] = 1
        if b:
            break
    if k%n == 0:
        print(0)
    else:
        print(2)
    for i in range(n):
        for j in range(n):
            print(mat[i][j], end="")
        print()


q = int(input())
for _ in range(q):
    n, k = list(map(int,input().split()))
    odp = [[0] * n for i in range(n)]
    cur = [0,0]
    zap = 0
    while True:
        if zap >= k:
            break
        odp[cur[0]][cur[1]] = 1
        zap += 1
        cur[0] = (cur[0]+1)%n
        cur[1] = (cur[1]+1)%n
        if cur[0] == 0:
            cur[1] = zap//n
    if k%n == 0:
        print(0)
    else:
        print(2)
    for i in range(n):
        print("".join(list(map(str,odp[i]))))


for _ in range(int(input())):
    n,k=list(map(int,input().split()))
    ans=[["0" for j in range(n)] for i in range(n)]
    posx=0
    posy=0
    count=k
    while count:
        ans[posx][posy]="1"
        count-=1
        if (k-count)%n!=0:
            posx=(posx+1)%n
            posy=(posy+1)%n
        else:
            posx=(posx+1)%n
            posy=(posy+2)%n

    res=0
    R=[sum(int(ans[i][j]) for j in range(n)) for i in range(n)]
    C=[sum(int(ans[i][j]) for i in range(n)) for j in range(n)]
    res=(max(R)-min(R))**2+(max(C)-min(C))**2
    print(res)
    for i in range(n):
        print("".join(ans[i]))


mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    for _ in range(int(input())):
        N, K = list(map(int, input().split()))
        if K % N == 0:
            print(0)
        else:
            print(2)
        ans = [[0] * N for _ in range(N)]
        cnt = 0
        flg = 0
        for p in range(N):
            if flg:
                break
            for i in range(N):
                if cnt == K:
                    flg = 1
                    break
                ans[i][(i+p)%N] = 1
                cnt += 1
        for i in range(N):
            print("".join(map(str, ans[i])))


def __starting_point():
    main()

__starting_point()

import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
# (N, K) = map(int, lines[0].strip().split(" "))
for t in range(T):
    (a, b) = map(int, lines[t+1].strip().split(" "))
    res = [[0 for _ in range(a)] for _ in range(a)]
    rema = b % a
    deno = b // a
    if rema == 0: val = 0
    else: val = 2
    for i in range(a):
        if i < rema:
            for j in range(deno+1):
                res[i][(i+j)%a] = 1
        else:
            for j in range(deno):
                res[i][(i+j)%a] = 1
    print(val)
    for i in range(a):
        print(''.join(map(str, res[i])))

import sys
input = sys.stdin.readline
for f in range(int(input())):
    n,k=list(map(int,input().split()))
    sm=k//n
    bg=sm
    toad=k%n
    if toad!=0:
        bg+=1
    print(2*(bg-sm)**2)
    for i in range(n):
        line=""
        for j in range(n):
            x=i+j
            x%=n
            if x<=sm:
                if x<sm or i<toad:
                    line+="1"
                else:
                    line+="0"
            else:
                line+="0"
        print(line)


t=int(input())
for _ in range(t):
  n,k=map(int,input().split())
  a=k//n
  rem=k%n
  grid=[]
  for i in range(n):
    grid.append([])
    for j in range(n):
      grid[-1].append('0')
  for i in range(n):
    for j in range(i,i+a):
      grid[i][j%n]='1'
    if i<rem:
      grid[i][(i+a)%n]='1'
  ans=0
  r=[]
  for i in range(n):
    p=0
    for j in range(n):
      if grid[i][j]=='1':
        p+=1
    r.append(p)
  c=[]
  for i in range(n):
    p=0
    for j in range(n):
      if grid[j][i]=='1':
        p+=1
    c.append(p)
  print((max(r)-min(r))**2+(max(c)-min(c))**2)
  for i in range(n):
    ans=''.join(grid[i])
    print(ans)

import sys
input=lambda: sys.stdin.readline().rstrip()
t=int(input())
for _ in range(t):
  n,k=map(int,input().split())
  if k%n==0:
    print(0)
  else:
    print(2)
  for i in range(n):
    ans=""
    if i<k%n:
      ans="1"*(k//n+1)+"0"*(n-(k//n+1))
      ans=ans[i:]+ans[:i]

    else:
      ans="1"*(k//n)+"0"*(n-(k//n))
      ans=ans[i:]+ans[:i]
    print(ans)

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
  n,k = map(int,input().split())
  if k%n:
    print(2)
  else:
    print(0)
  ans = [[0 for i in range(n)] for j in range(n)]
  if k == 0:
    for i in ans:
      print(*i,sep="")
    continue
  for i in range(n):
    for j in range(n):
      ans[j][(i+j)%n] = 1
      k -= 1
      if k == 0:
        break
    else:
      continue
    break
  for i in ans:
    print(*i,sep="")

import sys
input=sys.stdin.readline
t=int(input())
for i in range(t):
    n,k=map(int,input().split())
    m=k//n
    r=k%n
    if r:
        print(2)
        s='1'*(m+1)+'0'*(n-m-1)
        for i in range(r):
            print(s)
            s=s[1:]+s[0]
        i=(m-r)%n
        s=s[:i]+'0'+s[i+1:]
        for i in range(n-r):
            print(s)
            s=s[1:]+s[0]
    else:
        print(0)
        s='1'*m+'0'*(n-m)
        for i in range(n):
            print(s)
            s=s[1:]+s[0]

def solve():
    n, m = map(int, input().split())
    ans = 2 if m % n else 0
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        if m <= 0:
            break
        for j in range(n):
            if m <= 0:
                break
            a[j][(i + j) % n] = 1
            m -= 1
    print(ans)
    for i in a:
        print(*i, sep='')

t = int(input())
for _ in range(t):
    solve()

t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    board=[[0]*n for _ in range(n)]
    cnt=0
    for i in range(n):
        for j in range(n):
            if cnt==k:
                break
            board[(j+i)%n][j]=1
            cnt+=1
        if cnt==k:
            break
    if k%n==0:
        print(0)
    else:
        maxs=(k+n-1)//n
        mins=k//n
        print(2*((maxs-mins)**2))
    for i in range(n):
        print(''.join(map(str,board[i])))

import sys
input = sys.stdin.readline

import math

T = int(input())


def f(M):
    minR = math.inf
    maxR = -math.inf
    minC = math.inf
    maxC = -math.inf

    for i in range(len(M)):
        sumRow = sum(M[i])
        minR = min(minR, sumRow)
        maxR = max(maxR, sumRow)

        sumCol = sum([M[el][i] for el in range(len(M))])
        maxC = max(maxC, sumCol)
        minC = min(minC, sumCol)

    return (maxR - minR)**2 + (maxC - minC)**2

for t in range(T):
    N, K = [int(_) for _ in input().split()]
    M = [[0] * N for i in range(N)]

    # save = set()

    for i in range(K):
        # assert (i%N, (i//N + i)%N) not in save
        # save.add((i%N, (i//N + i)%N))
        M[i%N][(i//N + i)%N] = 1

    print(f(M))
    for row in M:
        print(''.join(map(str, row)))


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n,k=list(map(int,input().split()))

    ANS=[[0]*n for i in range(n)]

    o=k//n
    m=k-o*n

    now=0
    for i in range(n):
        if i<m:
            for j in range(o+1):
                ANS[i][now]=1
                now=(now+1)%n

        else:
            for j in range(o):
                ANS[i][now]=1
                now=(now+1)%n

    if m==0:
        print(0)
    else:
        print(2)

    for ans in ANS:
        print("".join(map(str,ans)))
        
    

    
    


import sys
input = sys.stdin.readline
for _ in range(int(input())):
  n, k = map(int, input().split())
  res = [["0"] * n for _ in range(n)]
  if k % n: print(2)
  else: print(0)
  for d in range(n):
    for i in range(n):
      if k == 0: break
      res[i][(i + d) % n] = "1"
      k -= 1
  for r in res: print("".join(r))


tt = int(input())

for loop in range(tt):

    n,k = list(map(int,input().split()))

    lis = [ [0] * n for i in range(n) ]

    ns = 0
    for si in range(n):

        if ns == k:
            break

        for i in range(n):

            lis[(si+i)%n][i] = 1
            ns += 1

            if ns == k:
                break
        else:
            continue
        break

    R = []
    for i in range(n):
        now = 0
        for j in range(n):
            now += lis[i][j]
        R.append(now)

    C = []
    for i in range(n):
        now = 0
        for j in range(n):
            now += lis[j][i]
        C.append(now)

    print((max(R)-min(R))**2 + (max(C)-min(C))**2)
    for i in lis:
        print("".join(map(str,i)))


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    table = [[0 for i in range(n)] for j in range(n)]
    if k % n == 0:
        print(0)
    else:
        print(2)
    i = 0
    j = 0
    bias = 0
    for __ in range(k):
        table[i][j % n] = 1
        i += 1
        j += 1
        if i >= n:
            bias += 1
            i = 0
            j = bias
    for i in table:
        print(''.join(map(str, i)))

for __ in range(int(input())):
    n, k = list(map(int, input().split()))
    ans = [[0] * n for i in range(n)]
    i, j = 0, 0
    while k > 0:
        while i < n and k > 0:
            ans[i][j] = 1
            i += 1
            j += 1
            k -= 1
            j %= n
        i = 0
        j += 1
    a1, a2, b1, b2 = 10 ** 9, 0, 10 ** 9, 0
    for i in range(n):
        a1 = min(a1, ans[i].count(1))
        a2 = max(a2, ans[i].count(1))
    for i in range(n):
        kek1 = 0
        for j in range(n):
            if ans[j][i] == 1:
                kek1 += 1
        b1 = min(b1, kek1)
        b2 = max(b2, kek1)
    print((a2 - a1) ** 2 + (b2 - b1) ** 2)
    for elem in ans:
        print(''.join(map(str, elem)))

def solve(n, k):
    matrix = [[0 for _ in range(n)] for _ in range(n)]
    for right_move in range(n):
        for height in range(n):
            if k == 0:
                continue
            i = height
            j = (height + right_move) % n
            matrix[i][j] = 1
            k -= 1
    return matrix


def get_value(matrix):
    n = len(matrix)
    max_r = 0
    min_r = n
    max_c = 0
    min_c = n
    for line in matrix:
        value = sum(line)
        max_r = max(max_r, value)
        min_r = min(min_r, value)
    for j in range(n):
        value = sum([matrix[i][j] for i in range(n)])
        max_c = max(max_c, value)
        min_c = min(min_c, value)
    res = (max_r - min_r) ** 2
    res += (max_c - min_c) ** 2
    return res


T = int(input())
for _ in range(T):
    n, k = list(map(int, input().split()))
    matrix = solve(n, k)
    value = get_value(matrix)
    print(value)
    for line in matrix:
        print(''.join(map(str, line)))


import math
import sys
t = int(input())
result = []
for cs in range(t):
    n, k = list(map(int, input().split()))
    a = [[0] * n for _ in range(n)]
    result.append('0' if k % n == 0 else '2')
    for i in range(n):
        cur = 0
        while cur < n and k > 0:
            a[cur][(i + cur) % n] = 1
            k -= 1
            cur += 1
    for i in range(n):
        result.append(''.join(map(str, a[i])))
print('\n'.join(result))




t = int(input())
for test in range(t):
    n,k = [int(i) for i in input().split()]
    tab = [["0" for c in range(n)] for r in range(n)]
    row = 0
    col = 0
    while k>0:
        tab[row][col] = "1"
        row = (row+1)%n
        col += 1
        if col==n:
            col = 0
            row = (row+1)%n
        k -= 1
    if col==0:
        print(0)
    else:
        print(2)
    for row in range(n):
        print(''.join(tab[row]))

import sys
input = sys.stdin.readline
inputr = lambda: sys.stdin.readline().rstrip('\n')

for _ in range(int(input())):
	n, k = list(map(int, input().split()))

	e = k // n
	T = [[0] * n for _ in range(n)]

	for i in range((k+n-1)//n):
		for j in range(min(n, k - i * n)):
			T[j][(i + j)%n] = 1

	rows = [sum(R) for R in T]
	cols = [sum(C) for C in zip(*T)]
	assert sum(rows) == k
	assert sum(cols) == k
	print((max(rows) - min(rows)) ** 2 + (max(cols) - min(cols)) ** 2)
	for R in T:
		print(''.join(map(str, R)))