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>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <cstring>
#include <iostream>
#define pie acos(-1)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sl(a) scanf("%lld",&a)
#define sll(a,b) scanf("%lld %lld",&a,&b)
#define slll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define ss(st) scanf("%s",st)
#define sch(ch) scanf("%ch",&ch)
#define ps(a) printf("%s",a)
#define newLine() printf("\n")
#define pi(a) printf("%d",a)
#define pii(a,b) printf("%d %d",a,b)
#define piii(a,b,c) printf("%d %d %d",a,b,c)
#define pl(a) printf("%lld",a)
#define pll(a,b) printf("%lld %lld",a,b)
#define plll(a,b,c) printf("%lld %lld %lld",a,b,c)
#define pd(a) printf("%lf",a)
#define pdd(a,b) printf("%lf %lf",a,b)
#define pddd(a,b,c) printf("%lf %lf %lf",a,b,c)
#define pch(c) printf("%ch",c)
#define debug1(str,a) printf("%s=%d\n",str,a)
#define debug2(str1,str2,a,b) printf("%s=%d %s=%d\n",str1,a,str2,b)
#define debug3(str1,str2,str3,a,b,c) printf("%s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c)
#define debug4(str1,str2,str3,str4,a,b,c,d) printf("%s=%d %s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c,str4,d)
#define for0(i,n) for(i=0;i<n;i++)
#define for1(i,n) for(i=1;i<=n;i++)
#define forab(i,a,b) for(i=a;i<=b;i++)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define nl puts("")
#define sd(a) scanf("%lf",&a)
#define sdd(a,b) scanf("%lf %lf",&a,&b)
#define sddd(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
#define sp printf(" ")
#define ll long long int
#define ull unsigned long long int
#define MOD 1000000007
#define mpr make_pair
#define pub(x) push_back(x)
#define pob(x) pop_back(x)
#define mem(ara,value) memset(ara,value,sizeof(ara))
#define INF INT_MAX
#define eps 1e-9
#define checkbit(n, pos) (n & (1<<pos))
#define setbit(n, pos) (n  (1<<pos))
#define para(i,a,b,ara)\
for(i=a;i<=b;i++){\
    if(i!=0){printf(" ");}\
    cout<<ara[i];\
}\
printf("\n");
#define pvec(i,vec)\
for(i=0;i<vec.size();i++){\
    if(i!=0){printf(" ");}\
    cout<<vec[i];\
}\
printf("\n");
#define ppara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
    for(j=0;j<m;j++){\
        if(j!=0){printf(" ");}\
        cout<<ara[i][j];\
    }\
    printf("\n");\
}
#define ppstructara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
    printf("%d:\n",i);\
    for(j=0;j<m;j++){\
        cout<<ara[i][j];printf("\n");\
    }\
}
#define ppvec(i,j,n,vec)\
for(i=0;i<n;i++){\
    printf("%d:",i);\
    for(j=0;j<vec[i].size();j++){\
        if(j!=0){printf(" ");}\
        cout<<vec[i][j];\
    }\
    printf("\n");\
}
#define ppstructvec(i,j,n,vec)\
for(i=0;i<n;i++){\
    printf("%d:",i);\
    for(j=0;j<vec[i].size();j++){\
        cout<<vec[i][j];printf("\n");\
    }\
}
#define sara(i,a,b,ara)\
for(i=a;i<=b;i++){\
    scanf("%d",&ara[i]);\
}
#define pstructara(i,a,b,ara)\
for(i=a;i<=b;i++){\
    cout<<ara[i];nl;\
}
#define pstructvec(i,vec)\
for(i=0;i<vec.size();i++){\
    cout<<vec[i];nl;\
}
#define pstructstl(stl,x)\
for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
    x=*it;\
    cout<<x;nl;\
}\
nl;
#define pstl(stl)\
for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
    if(it!=stl.begin()){sp;}\
    pi(*it);\
}\
nl;
#define ppairvec(i,vec)\
for(i=0;i<vec.size();i++){\
    cout<<vec[i].first;sp;cout<<vec[i].second;printf("\n");\
}
#define ppairara(i,a,b,ara)\
for(i=a;i<=b;i++){\
    cout<<ara[i].first;sp;cout<<ara[i].second;printf("\n");\
}
#define pppairvec(i,j,n,vec)\
for(i=0;i<n;i++){\
    printf("%d:\n",i);\
    for(j=0;j<vec[i].size();j++){\
        cout<<vec[i][j].first;sp;cout<<vec[i][j].second;nl;\
    }\
}
#define pppairara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
    printf("%d:\n",i);\
    for(j=0;j<m;j++){\
        cout<<ara[i][j].first;printf(" ");cout<<ara[i][j].second;nl;\
    }\
}
#define SZ 2 * 100010
#define xx first
#define yy second
using namespace std;
//using namespace __gnu_pbds;
//bool status[100010];
//vector <int> prime;
//void siv(){
//    int N = 100005, i, j; prime.clear();
//    int sq = sqrt(N);
//    for(i = 4; i <= N; i += 2){ status[i] = true; }
//    for(i = 3; i <= sq; i+= 2){
//        if(status[i] == false){
//            for(j = i * i; j <= N; j += i){ status[j] = true; }
//        }
//    }
//    status[1] = true;
//    for1(i, N){ if(!status[i]){ prime.pub(i); } }
//}
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//std::mt19937 mt(seed);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int add(int _a, int _b){
    if(_a < 0){ _a += MOD; }
    if(_b < 0){ _b += MOD; }
    if(_a + _b >= MOD){ return _a + _b - MOD; }
    return _a + _b;
}
inline int mul(int _a, int _b){
    if(_a < 0){ _a += MOD; }
    if(_b < 0){ _b += MOD; }
    return ((ll)((ll)_a * (ll)_b)) % MOD;
}
const int N = 1e5, M = 1500;
int m, k, a[N + 5], grid[M + 5][M + 5];  
vector < pair <int, int > > sorted; 
bool ok(int i, int j, int n, int x){
	if(i - 1 >= 0 && j - 1 >= 0 && grid[i - 1][j - 1] == x) return false; 
	if(i - 1 >= 0 && j + 1 <= n - 1 && grid[i - 1][j + 1] == x) return false; 
	if(i + 1 <= n - 1 && j - 1 >= 0 && grid[i + 1][j - 1] == x) return false; 
	if(i + 1 <= n - 1 && j + 1 <= n - 1 && grid[i + 1][j + 1] == x) return false; 
	return true;
}
bool test(int n){
	int i, j, l, cnt = 0; 
	vector < pair <int, int > > vec = sorted; 
	for(i = 0; i < n; ++i){
		for(j = 0; j < n; ++j){
			grid[i][j] = -1; 
		}
	}
	for(i = l = 0; i < n && l < vec.size(); i += 2){
		for(j = 1; j < n && l < vec.size(); j += 2){
			for(; l < vec.size(); ++l){
				if(!vec[l].xx) continue; 
				if(!ok(i, j, n, vec[l].yy)) continue; 
				break; 
			}
			if(l < vec.size()){
				grid[i][j] = vec[l].yy; 
				vec[l].xx--; 
				cnt++; 
			}
		}
	}
	if(cnt == m) return true;
	for(i = 1; i < n && l < vec.size(); i += 2){
		for(j = 0; j < n && l < vec.size(); j += 2){
			for(; l < vec.size(); ++l){
				if(!vec[l].xx) continue; 
				if(!ok(i, j, n, vec[l].yy)) continue; 
				break; 
			}
			if(l < vec.size()){
				grid[i][j] = vec[l].yy; 
				vec[l].xx--; 
				cnt++; 
			}
		}
	}
	if(cnt == m) return true;
	for(i = l = 0; i < n && l < vec.size(); i += 2){
		for(j = 0; j < n && l < vec.size(); j += 2){
			for(; l < vec.size(); ++l){
				if(!vec[l].xx) continue; 
				break; 
			}
			if(l < vec.size()){
				grid[i][j] = vec[l].yy; 
				vec[l].xx--; 
				cnt++; 
			}
		}
	}
	return (cnt == m); 
}
void solve(){
	int sqm = sqrt(m); 
    int i, j, lo = 1, hi = 3 * sqm; 
    sorted.clear(); 
    for(i = 0; i < k; ++i) sorted.push_back({a[i], i + 1}); 
    sort(sorted.begin(), sorted.end(), greater < pair <int, int > > ()); 
	while(lo < hi){
		int mid = (lo + hi) >> 1; 
		if(test(mid)) hi = mid; 
		else lo = mid + 1; 
	}
	pi(hi), nl; 
	bool f = test(hi); 
	for(i = 0; i < hi; ++i){
		for(j = 0; j < hi; ++j){
			if(j) sp; 
			pi(grid[i][j] == -1 ? 0 : grid[i][j]); 
		} nl; 
	}
}
int main(){
    // freopen("input.txt","r",stdin);
    // freopen("output.txt", "w", stdout);
    int cs, ts; 
    si(ts); 
    for0(cs, ts){
    	int i, j; 
    	sii(m, k); 
    	for(i = 0; i < k; ++i) si(a[i]); 
    	solve(); 
    }
}