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.math.*;
import java.util.*;

/**
 *
 * @author Saju
 *
 */

public class Main {

    private static int dx[] = { 1, 0, -1, 0 };
    private static int dy[] = { 0, -1, 0, 1 };

    private static final long INF = Long.MAX_VALUE;
    private static final int INT_INF = Integer.MAX_VALUE;
    private static final long NEG_INF = Long.MIN_VALUE;
    private static final int NEG_INT_INF = Integer.MIN_VALUE;
    private static final double EPSILON = 1e-10;

    private static final int MAX = 2000007;
    
    private static final long MOD = 1000000007;

    private static final int MAXN = 100007;
    private static final int MAXA = 10000009;
    private static final int MAXLOG = 22;

	public static void main(String[] args) throws IOException {

		InputReader in = new InputReader(System.in);
//		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

//         InputReader in = new InputReader(new FileInputStream("src/test.in"));
//         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("src/test.out")));

		
		
/*



*/
		
		int test = in.nextInt();
		for (int t = 1; t <= test; t++) {
			int n = in.nextInt();
			int k = in.nextInt();
			
			int[][] arr = new int[n][n];
			
			int sum = 0;
//			for(int p = 0; p < n; p++) {
//				for(int i = 0, j = p; i < n - p; i++, j++) {
//					if(sum == k) {
//						break;
//					}
//					arr[i][j] = 1;
//					sum++;
//				}
//				if(sum == k) {
//					break;
//				}
//			}
//			
//			for(int p = 1; p < n; p++) {
//				for(int i = p, j = 0; i < n; i++, j++) {
//					if(sum == k) {
//						break;
//					}
//					arr[i][j] = 1;
//					sum++;
//				}
//				if(sum == k) {
//					break;
//				}
//			}
			
			int uCount = 0;
			int dCount = 0;
			int r = n;
			int b = n;
			
			for(int p = 0; p < (2 * n) - 1; p++) {
				if(sum == k) {
					break;
				}
				if(p == 0) {
					for(int i = 0, j = 0; i < n; i++, j++) {
						arr[i][j] = 1;
						sum++;
						if(sum == k) {
							break;
						}
					}
					
				}
				else if(p % 2 == 1) {
					// up
					uCount++;
					for(int i = 0, j = uCount; i < n - uCount; i++, j++) {
						if(sum == k) {
							break;
						}
						arr[i][j] = 1;
						sum++;
					}
					// down
					b--;
					for(int i = b, j = 0; i < n; i++, j++) {
						if (sum == k) {
							break;
						}
						arr[i][j] = 1;
						sum++;
					}
					if(sum == k) {
						break;
					}
				}
				else {
					//down
					dCount++;
					for (int i = dCount, j = 0; i < n; i++, j++) {
						if (sum == k) {
							break;
						}
						arr[i][j] = 1;
						sum++;
					}			
					// up
					r--;
					for(int i = 0, j = r; j < n; i++, j++) {
						if (sum == k) {
							break;
						}
						arr[i][j] = 1;
						sum++;
					}
					if (sum == k) {
						break;
					}
				}
			}
			
//			for(int i = 0; i < n; i++) {
//				System.out.println(Arrays.toString(arr[i]));
//			}
			
			
			
			int minR = INT_INF;
			int maxR = 0;
			int minC = INT_INF;
			int maxC = 0;
			int row[] = new int[n];
			int col[] = new int[n];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					row[i] += arr[i][j];
				}
			}
			
//			System.out.println(Arrays.toString(row));
			for(int j = 0; j < n; j++) {
				for(int i = 0; i < n; i++) {
					col[j] += arr[i][j];
				}
			}
			for(int i = 0; i < n; i++) {
				minR = min(minR, row[i]);
				maxR = max(maxR, row[i]);
				minC = min(minC, col[i]);
				maxC = max(maxC, col[i]);
			}
//			System.out.println(Arrays.toString(col));
			
//			System.out.println(minR + " " + maxR + " " + minC + " " + maxC);
			
			int fa = (int) (Math.pow(maxR - minR, 2) + Math.pow(maxC - minC, 2));
			StringBuilder sb = new StringBuilder();
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					sb.append(arr[i][j]);
				}
				sb.append("\n");
			}
			
			out.println(fa);
			out.print(sb.toString());
		}
		
		
		
		
		
		in.close();
		out.flush();
		out.close();
		System.exit(0);
	}

	private static boolean isPalindrome(String str) {
		StringBuilder sb = new StringBuilder();
		sb.append(str);
		String str1 = sb.reverse().toString();
		return str.equals(str1);
	}

	private static String getBinaryStr(int n, int j) {
		String str = Integer.toBinaryString(n);
		int k = str.length();
		for (int i = 1; i <= j - k; i++) {
			str = "0" + str;
		}

		return str;
	}
	
	private static String getBinaryStr(long n, int j) {
		String str = Long.toBinaryString(n);
		int k = str.length();
		for (int i = 1; i <= j - k; i++) {
			str = "0" + str;
		}

		return str;
	}
	
	private static long bigMod(long n, long k, long m) {

        long ans = 1;
        while (k > 0) {
            if ((k & 1) == 1) {
                ans = (ans * n) % m;
            }
            n = (n * n) % m;
            k >>= 1;
        }
        return ans;
    }
    
	private static long ceil(long n, long x) {
		long div = n / x;
        if(div * x != n) {
            div++;
        }
        return div;
	}
	
    private static int ceil(int n, int x) {
        int div = n / x;
        if(div * x != n) {
            div++;
        }
        return div;
    }

    
    private static int abs(int x) {
        if (x < 0) {
            return -x;
        }
        return x;
    }

    private static long abs(long x) {
        if(x < 0) {
            return -x;
        }
        return x;
    }

    private static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    private static int gcd(int a, int b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    private static int log(long x, int base) {
        return (int) (Math.log(x) / Math.log(base));
    }

    private static long min(long a, long b) {
        if (a < b) {
            return a;
        }
        return b;
    }

    private static int min(int a, int b) {
        if (a < b) {
            return a;
        }
        return b;
    }

    private static long max(long a, long b) {
        if (a < b) {
            return b;
        }
        return a;
    }

    private static int max(int a, int b) {
        if (a < b) {
            return b;
        }
        return a;
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());

                }
            } catch (IOException e) {
                return null;
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String line = null;
            try {
                tokenizer = null;
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public boolean hasNext() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (Exception e) {
                return false;
            }
            return true;
        }
        
        public int[] nextIntArr(int n) {
        	int arr[] = new int[n];
    		for(int i = 0; i < n; i++) {
    			arr[i] = nextInt();
    		}
    		return arr;
        }
        
        public long[] nextLongArr(int n) {
        	long arr[] = new long[n];
    		for(int i = 0; i < n; i++) {
    			arr[i] = nextLong();
    		}
    		return arr;
        }
        
        public int[] nextIntArr1(int n) {
        	int arr[] = new int[n + 1];
    		for(int i = 1; i <= n; i++) {
    			arr[i] = nextInt();
    		}
    		return arr;
        }
        
        public long[] nextLongArr1(int n) {
        	long arr[] = new long[n + 1];
    		for(int i = 1; i <= n; i++) {
    			arr[i] = nextLong();
    		}
    		return arr;
        }
       
        public void close() {
        	try {
        		if(reader != null) {
        			reader.close();
        		}
        	}
        	catch(Exception e) {
        		
        	}
        	
        	
        }
    }

}