Problem: You like numbers, don't you? Nastia has a lot of numbers and she wants to share them with you! Isn't it amazing?

Let a_i be how many numbers i (1 ≤ i ≤ k) you have.

An n × n matrix is called beautiful if it contains all the numbers you have, and for each 2 × 2 submatrix of the original matrix is satisfied: 

  1. The number of occupied cells doesn't exceed 3; 
  2. The numbers on each diagonal are distinct. 



Make a beautiful matrix of minimum size.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains 2 integers m and k (1 ≤ m, k ≤ 10^5) — how many numbers Nastia gave you and the length of the array a, respectively.

The second line of each test case contains k integers a_1, a_2, …, a_{k} (0 ≤ a_i ≤ m, a_1 + a_2 + … + a_{k} = m), where a_i is how many numbers i you have.

It's guaranteed that the sum of m and k in one test doesn't exceed 2 ⋅ 10^5.

Output

For each t test case print a single integer n — the size of the beautiful matrix.

In the next n lines print n integers b_{i, j} (0 ≤ b_{i, j} ≤ k; if position is empty, print b_{i, j} = 0) — the beautiful matrix b you made up. 

Example

Input


2
3 4
2 0 0 1
15 4
2 4 8 1


Output


2
4 1
0 1
5
3 0 0 2 2
3 2 3 3 0
0 1 0 4 0
3 0 0 0 0
2 1 3 3 3

Note

Note that 0 in this problem represents a blank, not a number.

Examples of possible answers for the first test case:

\begin{array}{cc} 1 & 1 \\\ 4 & 0 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 4 \\\ 1 & 0 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 0 \\\ 1 & 1 \\\ \end{array}

Examples of not beautiful matrices for the first test case:

\begin{array}{cc} 1 & 0 \\\ 4 & 1 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 1 \\\ 7 & 1 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 0 \\\ 4 & 0 \\\ \end{array}

The example of the not beautiful matrix for the second test case:

\begin{array}{cc} 3 & 4 & 0 & 2 & 2 \\\ 3 & 2 & 3 & 3 & 0 \\\ 0 & 1 & 0 & 0 & 0 \\\ 3 & 0 & 0 & 0 & 0 \\\ 2 & 1 & 3 & 3 & 3 \\\ \end{array}

Everything is okay, except the left-top submatrix contains 4 numbers.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class E {
  static int HAS_TESTCASES = 1;
  static String INPUT = "2\n"+"3 1\n"+"1\n"+"15 4\n"+"2 4 8 1\n"+"";
  void solve(int cNr) {
    int m = nextInt();
    int k = nextInt();
    ArrayList<Long> a_in = nextLongList(k);
    long max_count = 0;
    long total_count = 0;
    int max_index = 0;
    for (int i = 0; i<k; i++) {
      long quan = a_in.get(i);
      total_count+=quan;
      if (quan>max_count) {
        max_count=quan;
        max_index=i;
      }
    }
    int n = 1;
    for (int i = 1; true; i++) {
      int capacity = i*i-(i/2)*(i/2);
      int max_capacity = i*((i+1)/2);
      if (total_count<=capacity&&max_count<=max_capacity) {
        n=i;
        break;
      }
    }
    LinkedList<Long> a = convert(a_in, max_index);
    long[][] mat = new long[n][n];
    fill1(mat, a);
    fill2(mat, a);
    fill3(mat, a);
    out.println(n);
    print(mat);
  }
  void fill1(long[][] mat, LinkedList<Long> a) {
    try {
      for (int i = 0; i<mat.length; i++) {
        for (int j = 0; j<mat.length; j++) {
          boolean exp = (i+j)%2==1&&i%2==0;
          if (exp)
            mat[i][j]=a.pop();
        }
      }
    } catch (Exception e) {
    }
  }
  void fill2(long[][] mat, LinkedList<Long> a) {
    try {
      for (int i = 0; i<mat.length; i++) {
        for (int j = 0; j<mat.length; j++) {
          boolean exp = (i+j)%2==0&&i%2==0;
          if (exp)
            mat[i][j]=a.pop();
        }
      }
    } catch (Exception e) {
    }
  }
  void fill3(long[][] mat, LinkedList<Long> a) {
    try {
      for (int i = 0; i<mat.length; i++) {
        for (int j = 0; j<mat.length; j++) {
          boolean exp = (i+j)%2==1&&i%2==1;
          if (exp)
            mat[i][j]=a.pop();
        }
      }
    } catch (Exception e) {
    }
  }
  static LinkedList<Long> convert(List<Long> a, int maxind) {
    LinkedList<Long> ret = new LinkedList<>();
    for (int j = 0; j<a.get(maxind); j++) {
      ret.add(maxind+1l);
    }
    a.set(maxind, 0l);
    for (int i = 0; i<a.size(); i++) {
      for (int j = 0; j<a.get(i); j++) {
        ret.add(i+1l);
      }
    }
    return ret;
  }
  static int nextInt() {
    return Integer.parseInt(nextString());
  }
  static long nextLong() {
    return Long.parseLong(nextString());
  }
  static ArrayList<Long> nextLongList(int n) {
    ArrayList<Long> a = new ArrayList<>();
    for (int i = 0; i<n; i++) {
      a.add(nextLong());
    }
    return a;
  }
  static String nextString() {
    tokens();
    return st.nextToken();
  }
  static void tokens() {
    while (!st.hasMoreTokens()) {
      try {
        st=new StringTokenizer(br.readLine());
      } catch (Exception e) {
        throw new RuntimeException("out of tokens!");
      }
    }
  }
  static void print(long[][] a) {
    for (int i = 0; i<a.length; i++) {
      for (int j = 0; j<a[i].length; j++) {
        out.print(a[i][j]+" ");
      }
      out.println();
    }
  }
  static BufferedReader br;
  static StringTokenizer st = new StringTokenizer("");
  static PrintWriter out = new PrintWriter(System.out);
  public static void main(String[] a) {
    if (System.getProperty("ONLINE_JUDGE")==null) {
      System.setIn(new ByteArrayInputStream(INPUT.getBytes()));
    }
    br=new BufferedReader(new InputStreamReader(System.in));
    int t = HAS_TESTCASES>0 ? nextInt() : 1;
    for (int i = 1; i<=t; i++) {
      new E().solve(i);
    }
    out.flush();
  }
}