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 fulcrum(...) ;
#ifndef promising
#define dump(...)
#endif

#define E 2.718281828459045
#define PI 3.141592653589793
#define M7 1000000007
#define M3 998244353
#define INF 0x3fffffff
#define INF64 0x3fffffff3fffffff

const int P=M3;

#define loop(i,n) for(int i=0;i<(n);i++)
#define lback(i,n) for(int i=(n)-1;i>=0;i--)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define rback(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define all(x) (x).begin(),(x).end()
#define tri(op,a,b,c) op(op(a,b),c)
#define isz(x) ((int)(x).size())
#define iln(x) ((int)(x).length())

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;
typedef pair<long long,long long> pll;
typedef complex<double> cp;
template<class T> using vector2D = vector<vector<T>>;
template<class T> using vector3D = vector<vector2D<T>>;

template<class T> bool umax(T &x, T y) { return (x<y)? x=y,true: false; }
template<class T> bool umin(T &x, T y) { return (x>y)? x=y,true: false; }

void prepare() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

const int maxn=1005;

int n,m;
int ans[maxn][maxn];

struct Good {
    vector2D<int> a;
    int n;
    int ux,uy,ue;
    int d1x,d1y,d1e;
    int d2x,d2y,d2e;
    Good(int n):n(n) {
        a.resize(n,vector<int>(n));
        ux=uy=0;
        d1x=d2y=0;
        d1y=d2x=1;
        ue=0;
        d1e=d2e=(1>=n);
    }
    pii getD1() {
        pii res(d1x,d1y);
        if((d1y+=2)>=n) d1y=1,d1x+=2;
        if(d1x>=n) d1e=1;
        return res;
    }
    pii getD2() {
        pii res(d2x,d2y);
        if((d2y+=2)>=n) d2y=0,d2x+=2;
        if(d2x>=n) d2e=1;
        return res;
    }
    pii getU() {
        pii res(ux,uy);
        if((uy+=2)>=n) uy=0,ux+=2;
        if(ux>=n) ue=1;
        return res;
    }
    void paint(int v) {
        auto [x,y]=(!d1e)? getD1(): (!ue)? getU(): getD2();
        a[x][y]=v;
    }
    void print() {
        cout<<n<<endl;
        loop(i,n) loop(j,n)
            cout<<a[i][j]<<" \n"[j==n-1];
    }
};

void solve() {
    cin>>m>>n;
    vector<pii> a(n);
    loop(i,n) cin>>a[i].first, a[i].second=i+1;
    sort(all(a),greater<pii>());

    ll mx=a[0].first, C;
    for(C=1;mx>C*((C+1)/2)||m>C*C-(C/2)*(C/2);C++);
    Good ans(C);
    for(auto [cnt,num]: a) loop(i,cnt) ans.paint(num);
    ans.print();
}

int main() {
    prepare();
    int T; cin>>T;
    loop(T_,T) solve();
    return 0;
}