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 CPP):

Solution:
#include <bits/stdc++.h>

#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i=1;i<=n;++i)
#define rrep(i,n) for(int i=0;i<n;++i)
#define srep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,s,t) for(int i=t;i>=s;--i)
#define DEBUG
#define d1(x) std::cout << #x " = " << (x) << std::endl
#define d2(x, y) std::cout << #x " = " << (x) << " ," #y " = " << (y) << std::endl
#define disp(arry, fr, to) \
    { \
        std::cout << #arry " : "; \
        for(int _i = fr; _i <= to; _i++) std::cout << arry[_i] << " "; \
        std::cout << std::endl; \
    }


using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 1e5+10;
const int Inf = 0x7f7f7f7f;
const ll Inf_ll = 1ll*Inf*Inf;
const int Mod = 1e9+7;
const double eps = 1e-7;

int k, n, a[Maxn];
int ans[1010][1010], hav[1010];

vector<pii> vp, v1, v2;
pii p[1010][1010];
int nn, mm[1010];

void solve(){
    scanf("%d %d",&k,&n);
    int Max = 0;
    vp.clear();
    for(int i=1;i<=n;i++)  scanf("%d",&a[i]), Max = max(Max, a[i]), vp.pb(mp(a[i], i));
    sort(all(vp), greater<pii>());
    int m = 1;
    for(int i=1;i<=1000;i++)
        if( Max <= i*((i+1)/2) && k <= hav[i] )
        {
            m = i;
            break;
        }
    
    nn = 0;
    for(int i=2;i<m;i+=2)
    {
        nn++, mm[nn] = 0;
        int x = i, y = 1;
        while( 233 )
        {
            p[nn][++mm[nn]] = mp(x, y);
            x--, y++;
            if( x < 1 )  break;
        }
    }
    int fi = 1;
    if( m&1 )  fi = 2;
    for(int j=fi;j<=m;j+=2)
    {
        nn++, mm[nn] = 0;
        int x = m, y = j;
        while( 233 )
        {
            p[nn][++mm[nn]] = mp(x, y);
            x--, y++;
            if( y > m )  break;
        }
    }
    if( m&1 )
    {
        for(int i=nn/2+1;i<=nn;i++)
            for(int j=1;j<=mm[i];j+=2)
                swap(p[i][j], p[i][j+1]);
    }
    // for(int i=1;i<=nn;i++,newline)  for(int j=1;j<=mm[i];j++)  printf("(%d, %d) ", p[i][j].first, p[i][j].second);

    for(int i=1;i<=m;i++)  for(int j=1;j<=m;j++)  ans[i][j] = 0;
    v1.clear(), v2.clear();

    for(int i=1;i<=nn;i++)  for(int j=1;j<=mm[i];j++)
    {
        if( j&1 )  v1.pb(p[i][j]);
        else v2.pb(p[i][j]);
    }    
    int x = 1, y = 1;
    reverse(all(v2));
    for(auto qwq:vp){
        while( !v1.empty() && qwq.first )
        {
            pii p = v1.back();
            ans[p.first][p.second] = qwq.second;
            qwq.first--;  v1.pop_back();
        }
        while( x <= m && qwq.first )
        {
            ans[x][y] = qwq.second;
            qwq.first--, y += 2;
            if( y > m )  x += 2, y = 1;
        }
        while( !v2.empty() && qwq.first )
        {
            pii p = v2.back();
            ans[p.first][p.second] = qwq.second;
            qwq.first--;  v2.pop_back();
        }
    }
    printf("%d\n", m);
    for(int i=1;i<=m;i++,newline)  for(int j=1;j<=m;j++)  printf("%d ", ans[i][j]);
}   

void init(){ 
    for(int i=1;i<=1000;i++)
        hav[i] = i*i - (i/2)*(i/2);
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    for(int _=1;_<=T;_++)
    {
        solve();
    }
    return 0;
}