Problem: 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 × 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 ≤ i ≤ n). 
  * C_j = A_{1,j}+A_{2,j}+...+A_{n,j} (for all 1 ≤ j ≤ 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 ≤ t ≤ 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 ≤ n ≤ 300, 0 ≤ k ≤ 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).

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;

public class Cf294 implements Runnable 
{
    static class InputReader 
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) 
        {
            this.stream = stream;
        }
        
        public int read()
        {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) 
            {
                curChar = 0;
                try
                {
                    numChars = stream.read(buf);
                }
                catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }    
            return str;
        }
        public int[] nextArray(int n)
        {
            int arr[] = new int[n];
            int i;
            for(i=0;i<n;i++)
            {
                arr[i] = nextInt();
            }
            return arr;
        }
        public int nextInt() 
        {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
        
            int sgn = 1;
        
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do
            {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
        
            return res * sgn;
        }
        
        public long nextLong() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }    
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') 
            {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') 
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
    
        public String readString() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next()
        {
            return readString();
        }
        
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
        
        public int[] nextIntArray(int n)
        {
            int i;
            int arr[] = new int[n];
            for(i=0;i<n;i++)
            {
                arr[i] = nextInt();
            }
            return arr;
        }
        
        public long[] nextLongArray(int n)
        {
            int i;
            long arr[] = new long[n];
            for(i=0;i<n;i++)
            {
                arr[i] = nextLong();
            }
            return arr;
        }
        
        public double[] nextDoubleArray(int n)
        {
            int i;
            double arr[] = new double[n];
            for(i=0;i<n;i++)
            {
                arr[i] = nextDouble();
            }
            return arr;
        }
        
        public Integer[] IntegerArray(int n)
        {
            int i;
            Integer arr[] = new Integer[n];
            for(i=0;i<n;i++)
            {
                arr[i] = nextInt();
            }
            return arr;
        }
        
        public Long[] LongArray(int n)
        {
            int i;
            Long arr[] = new Long[n];
            for(i=0;i<n;i++)
            {
                arr[i] = nextLong();
            }
            return arr;
        }
        
        public Double[] DoubleArray(int n)
        {
            int i;
            Double arr[] = new Double[n];
            for(i=0;i<n;i++)
            {
                arr[i] = nextDouble();
            }
            return arr;
        }
        
        public ArrayList<ArrayList<Integer>> getGraph(int n,int m)
        {
            ArrayList<ArrayList<Integer>> g =new ArrayList<>();
            int i;
            for(i=0;i<=n;i++)
            {
                g.add(new ArrayList<>());
            }
            for(i=0;i<m;i++)
            {
                int x = nextInt();
                int y = nextInt();
                g.get(x).add(y);
                g.get(y).add(x);
            }
            return g;
        }
        
        public ArrayList<ArrayList<Integer>> getTree(int n)
        {
            ArrayList<ArrayList<Integer>> g =new ArrayList<>();
            int i;
            for(i=0;i<=n;i++)
            {
                g.add(new ArrayList<>());
            }
            for(i=0;i<n-1;i++)
            {
                int x = nextInt();
                int y = nextInt();
                g.get(x).add(y);
                g.get(y).add(x);
            }
            return g;
        }
    }
    
    public static int maxInt(int arr[])
    {
        int max = Integer.MIN_VALUE;
        for(int i : arr)
        {
            max = Math.max(i,max);
        }
        return max;
    }
    
    public static int minInt(int arr[])
    {
        int min = Integer.MAX_VALUE;
        for(int i : arr)
        {
            min = Math.min(i,min);
        }
        return min;
    }
    
    public static long maxLong(long arr[])
    {
        long max = Long.MIN_VALUE;
        for(long i : arr)
        {
            max = Math.max(i,max);
        }
        return max;
    }
    
    public static long minLong(long arr[])
    {
        long min = Long.MAX_VALUE;
        for(long i : arr)
        {
            min = Math.min(i,min);
        }
        return min;
    }
    
    public static double maxDouble(double arr[])
    {
        double max = Double.MIN_VALUE;
        for(double i : arr)
        {
            max = Math.max(i,max);
        }
        return max;
    }
    
    public static double minDouble(double arr[])
    {
        double min = Double.MAX_VALUE;
        for(double i : arr)
        {
            min = Math.min(i,min);
        }
        return min;
    }
    
    void merge(int arr[], int l, int m, int r) 
    { 
        int n1 = m - l + 1; 
        int n2 = r - m; 
      

        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
      

        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
  
  
  

        int i = 0, j = 0; 
      

        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
            arr[k] = L[i]; 
            i++; 
            } 
            else
            { 
            arr[k] = R[j]; 
            j++; 
            } 
            k++; 
        } 

        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
      
   
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
  
    
    void sort(int arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            int m = (l+r)/2; 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    }
    
    static class Pair
    {
        int x,y;
        public Pair(int x,int y)
        {
            this.x = x;
            this.y = y;
        }
        public static Comparator<Pair> sortX = new Comparator<Pair>(){
            public int compare(Pair p1,Pair p2)
            {
                if(p1.x==p2.x)
                {
                    return p1.y-p2.y;
                }
                return p1.x-p2.x;
            }
        };
        
        public static Comparator<Pair> sortY = new Comparator<Pair>(){
            public int compare(Pair p1,Pair p2)
            {
                if(p1.y==p2.y)
                {
                    return p1.x-p2.x;
                }
                return p1.y-p2.y;
            }
        };
        
        public static Comparator<Pair> custom = new Comparator<Pair>(){
            public int compare(Pair p1,Pair p2)
            {
                if((p1.y-p1.x==p2.y-p2.x))
                    return (p1.x-p2.x);
                return ((p2.y-p2.x)-(p1.y-p2.x));
            }
        };
        
        public boolean equals(Object obj) 
        {
            if (obj == null) return false;
            if (!(obj instanceof Pair))
                return false;
            return (this.x == ((Pair) obj).x && this.y == ((Pair)obj).y);
        }

        public int hashCode()
        {
            if(x<0 || y<0)
            {
                return -5*x+-32*y;
            }
            return 5*(x+y);
        }
    }
    
    static class DPair
    {
        Pair s,d;
        public DPair(Pair s,Pair d)
        {
            this.s = s;
            this.d = d;
        }
        
        public boolean equals(Object obj) 
        {
            if (obj == null) return false;
            if (!(obj instanceof DPair))
                return false;
            return (this.s.x == ((DPair) obj).s.x && this.s.y == ((DPair) obj).s.y && this.d.x == ((DPair)obj).d.x && this.d.y == ((DPair) obj).d.y);
        }
        public int hashCode()
        {
            return 5*(s.x+s.y+d.x+d.y);
        }
    }
    
    static class DSU
    {
        public static int rank[],parent[];
        int n;
        HashMap<Integer,Integer> map = new HashMap<>();
        
        public DSU(int n)
        {
            rank = new int[n+1];
            parent = new int[n+1];
            this.n = n;
            makeSet(n);
        }
        
        public void makeSet(int n)
        {
            for(int i=1;i<=n;i++)
            {
                parent[i] = i;
                map.put(i,1);
            }
        }
        
        public static int find(int x)
        {
            if(parent[x]!=x)
            {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void union(int x,int y)
        {
            int xRoot = find(x);
            int yRoot = find(y);
            
            if(xRoot==yRoot)
            {
                return;
            }
            
            if(rank[xRoot] < rank[yRoot])
            {
                parent[xRoot] = yRoot;
                map.put(yRoot,map.getOrDefault(yRoot,1)+map.getOrDefault(xRoot,1));
                if(map.getOrDefault(xRoot,0)!=0)
                {
                    map.remove(xRoot);
                }
            }
            else if(rank[yRoot] < rank[xRoot])
            {
                parent[yRoot] = xRoot;
                map.put(xRoot,map.getOrDefault(xRoot,1) + map.getOrDefault(yRoot,1));
                if(map.getOrDefault(yRoot,0)!=0)
                {
                    map.remove(yRoot);
                }
            }
            else
            {
                parent[yRoot] = xRoot;
                rank[xRoot] = rank[xRoot] + 1;
                map.put(xRoot,map.getOrDefault(xRoot,1)+map.getOrDefault(yRoot,1));
                if(map.getOrDefault(yRoot,0)!=0)
                {
                    map.remove(yRoot);
                }
            }
        }
    }
        
    public static void main(String args[]) throws Exception 
    {
        new Thread(null, new Cf294(),"Main",1<<27).start();
    }    
    
  
    
    public void run()    
    {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
        int t = sc.nextInt();
        while(t-->0)
        {
            int n=sc.nextInt();
            int o=sc.nextInt();
            int fa=0;
        int[][] ar = new int[n][n];
        if(o==0)
        {
           fa=0;
        }
        else{
             int temp=o;
        for(int i=0; o>0 && i<n; i++){
            int r=0;
            int c=i;
            for(int k=0; o>0 && k<n; k++){
                ar[r][c]=1;
                o--;
                r= (r+1)%n;
                c=(c+1)%n;
            }
         }
         fa= temp%n==0? 0 : 2;
        }
       
      
        
       
        w.println(fa);
        
             for(int i=0; i<ar.length; i++){
                for(int j=0; j<ar[0].length; j++){
                    w.print(ar[i][j]);
                }
                w.println();
            }
            
        }
        w.flush();
        w.close();
    }
    
   
}