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.*;

/**
 *              _,--"^^"-.,_
         _.-"~^`~-.    .-~`^~"-._
     ,="`"-._     .----.     _.-"`"=,
    ;_       "-. (0 )( 0) .-"       _;
   .' `~"=,_    '.\ \/ /.'    _,="~` `.
   ;_       "-. _.-)  (-._ .-"       _;
   : ^~"-.,___.'  (    )  `.___,.-"~^ ;
   :        _:     `--'     :_        :
    '._,-~"` :':          :': `"~-,_.'
       '.,_.-`.            .'`-._,.'
          :__.-`-.______.-'`-.__;
                 //    \\
               (((~    ~)))
 */
 
public class A{
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }
    // main solver
    static class Task{

        double eps= 0.00000001;
        static final int MAXN = 10000001; 
       
        // stores smallest prime factor for every number 
        static int spf[] = new int[MAXN]; 

        Map<Integer,Set<Integer>> dp= new HashMap<>();
        
        // Calculating SPF (Smallest Prime Factor) for every 
        // number till MAXN. 
        // Time Complexity : O(nloglogn) 
        public void sieve() 
        { 
            spf[1] = 1; 
            for (int i=2; i<MAXN; i++) 
        
                // marking smallest prime factor for every 
                // number to be itself. 
                spf[i] = i; 
        
            // separately marking spf for every even 
            // number as 2 
            for (int i=4; i<MAXN; i+=2) 
                spf[i] = 2; 
        
            for (int i=3; i*i<MAXN; i++) 
            { 
                // checking if i is prime 
                if (spf[i] == i) 
                { 
                    // marking SPF for all numbers divisible by i 
                    for (int j=i*i; j<MAXN; j+=i) 
        
                        // marking spf[j] if it is not  
                        // previously marked 
                        if (spf[j]==j) 
                            spf[j] = i; 
                } 
            } 
        } 
        
        // A O(log n) function returning primefactorization 
        // by dividing by smallest prime factor at every step 
        public Set<Integer> getFactorization(int x) 
        { 
            if(dp.containsKey(x)) return dp.get(x);
            Set<Integer> ret = new HashSet<>(); 
            while (x != 1) 
            { 
                if(spf[x]!=2) ret.add(spf[x]); 
                x = x / spf[x]; 
            } 
            dp.put(x,ret);
            return ret; 
        } 
        // function to find first index >= x 
        public int lowerIndex(List<Integer> arr, int n, int x) 
        { 
            int l = 0, h = n - 1; 
            while (l <= h)  
            { 
                int mid = (l + h) / 2; 
                if (arr.get(mid) >= x) 
                    h = mid - 1; 
                else
                    l = mid + 1; 
            } 
            return l; 
        } 
        
        // function to find last index <= y 
        public int upperIndex(List<Integer> arr, int n, int y) 
        { 
            int l = 0, h = n - 1; 
            while (l <= h)  
            { 
                int mid = (l + h) / 2; 
                if (arr.get(mid) <= y) 
                    l = mid + 1; 
                else
                    h = mid - 1; 
            } 
            return h; 
        } 
        
        // function to count elements within given range 
        public int countInRange(List<Integer> arr, int n, int x, int y) 
        { 
            // initialize result 
            int count = 0; 
            count = upperIndex(arr, n, y) -  
                    lowerIndex(arr, n, x) + 1; 
            return count; 
        }
        
        public void solve(InputReader in, PrintWriter out) {           
            int t=in.nextInt();
            while(t-->0){
                int m= in.nextInt(), k= in.nextInt();
                List<Pair> arr= new ArrayList<>();
                for(int i=1;i<=k;i++){
                    arr.add(new Pair(in.nextInt(),i));
                }
                Collections.sort(arr, Collections.reverseOrder());
                int size= (int)Math.ceil(Math.sqrt(m));
                while(size*size-(size/2)*(size/2)<m) size++;
                // out.println("size: "+size);
                while(arr.get(0).x>Math.ceil((double)size/2)*size) size++;
                int[][] mat= new int[size][size];
                List<Pair> coor= new ArrayList<>();
                for(int i=1;i<size;i+=2){
                    for(int j=0;j<size;j+=2){
                        coor.add(new Pair(i,j));
                    }
                }
                for(int i=0;i<size;i+=2){
                    for(int j=0;j<size;j+=2){
                        coor.add(new Pair(i,j));
                    }
                }
                for(int i=0;i<size;i+=2){
                    for(int j=1;j<size;j+=2){
                        coor.add(new Pair(i,j));
                    }
                }
                int idx=0;
                for(Pair p: arr){
                    for(int i=0;i<p.x;i++,idx++){
                        mat[coor.get(idx).x][coor.get(idx).y]=p.y;
                    }
                }
                out.println(size);
                for(int i=0;i<size;i++){
                    for(int j=0;j<size;j++){
                        out.print(mat[i][j]+" ");
                    }
                    out.println();
                }
                
            }

        }
        public int _gcd(int a,  int  b)
        {
        
            if(b == 0) {
                    return a;
            }
            else {
                return _gcd(b, a % b);
            }
        }

    }

    static class Tuple implements Comparable<Tuple>{
        int x, y, z;
        public Tuple(int x, int y, int z){
            this.x= x;
            this.y= y;
            this.z=z;
        }
        @Override
        public int compareTo(Tuple o){
            return this.x-o.x;
        }
    }

    static class Pair implements Comparable<Pair>{
        public int x;
        public int y;
        public Pair(int x, int y){
            this.x= x;
            this.y= y;
        }
 
        @Override
        public int compareTo(Pair o) {
            return this.x-o.x;
        }
    }
    // fast input reader class;
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
 
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }
 
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        public double nextDouble(){
            return Double.parseDouble(nextToken());
        }
        public long nextLong(){
            return Long.parseLong(nextToken());
        }
    }
}