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 <numeric>
#include <ctime>
using namespace std;

#define M1 1000069
#define M2 998244353
#define M3 1000000007
#define M4 1000000009
#define PI 3.141592653589793238462643383279
#define EPS 1e-9
#define INF LLONG_MAX

// _________________________USED OFTEN_________________________

#define ll long long
#define ull unsigned long long int;
#define ldb long double;
#define loop(a, b, c) for (ll a = b; a < c; a++)
#define rloop(a, b, c) for (ll a = b; a >= c; a--)

#define clr(ar, x) memset(ar, x, sizeof(ar))
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front()
#define si size()
#define be begin()
#define en end()
#define all(v) v.be, v.en
#define le length()
#define mp make_pair
#define mt make_tuple
#define acc(v) accumulate(all(v), 0)
#define cnt count
#define in insert
#define er erase
#define F first
#define S second

#define lb lower_bound
#define ub upper_bound
#define eqr equal_range
#define bs binary_search
#define np next_permutation

#define nl cout << "\n"
#define P0(a) cout << a << " "
#define P1(a) cout << a << "\n"
#define P2(a, b) cout << a << " " << b << "\n"
#define P3(a, b, c) cout << a << " " << b << " " << c << "\n"
#define P4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << "\n"

#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
#define max4(a, b, c, d) max(a, max3(b, c, d))
#define min4(a, b, c, d) min(a, min3(b, c, d))
#define max5(a, b, c, d, e) max(max4(a, b, c, d), e)
#define min5(a, b, c, d, e) min(min4(a, b, c, d), e)

#define findnot find_first_not_of
#define gcd __gcd
#define deci(n) fixed << setprecision(n)
#define high(n) __builtin_popcount(n)
#define highll(n) __builtin_popcountll(n)
#define parity(n) __builtin_parity(n)
#define clz(n) __builtin_clz(n)
#define clzll(n) __builtin_clzll(n)
#define ctz(n) __builtin_ctz(n)

// _________________________DATA STRUCTURES_________________________

#define pii pair<int, int>;
#define pll pair<ll, ll>

#define vi vector<int>
#define vc vector<char>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvll vector<vll>

#define mli map<ll, int>
#define mll map<ll, ll>

#define sll set<ll>
#define sc set<char>

#define msc multiset<char>
#define msi multiset<int>
#define msll multiset<ll>

// _________________________TRAVERSING AND SORTING_________________________

#define minAll(v) *min_element(all(v))
#define maxAll(v) *max_element(all(v))

#define Sort(ar, n) sort(ar, ar + n)
#define rSort(ar, n) sort(ar, ar + n, greater<ll>())

#define Sortv(v) sort(all(v))
#define rSortv(v) sort(all(v), greater<ll>())

// _________________________FUNCTIONS_________________________

ll modulo(ll a, ll n, ll p = M1)
{
    ll ret = 1;
    a %= p;

    while (n)
    {
        if (n & 1)
        {
            ret = ((ret * a) % p);
        }

        n >>= 1;
        a = ((a * a) % p);
    }
    return ret;
}

ll modadd(ll a, ll b, ll m = M1)
{
    return (((a % m) + (b % m)) % m);
}

ll modmul(ll a, ll b, ll m = M1)
{
    return (((a % m) * (b % m)) % m);
}

ll modinv(ll a, ll m = M1)
{
    return modulo(a, m - 2, m);
}

ll inverse(ll i, ll m = M1)
{
    if (i == 1)
    {
        return 1;
    }

    return (m - ((m / i) * inverse(m % i, m)) % m + m) % m;
}

// _________________________CODE_________________________
long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// Function to return LCM of two numbers
long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
//////////////////////////////////////////////////////////////////////

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        // cout<<"hello";
        int m, k1;
        cin >> m >> k1;

        int a[k1 + 1];
        a[0] = 0;
        loop(i, 1, k1 + 1) cin >> a[i];
        int mx = a[1];
        int mi = 1;
        loop(i, 1, k1 + 1)
        {
            if (mx < a[i])
            {
                mx = a[i];
                mi = i;
            }
        }

        int n = 0;
        while (1)
        {
            // cout << n << " ";
            n++;
            if (n * n - (n / 2) * (n / 2) >= m && n * ceil((double)n / 2) >= mx)
            {
                break;
            }
        }
        cout << n << endl;
        // swap(a[mi],a[1]);
        int cur = mi;
        vector<vector<int>> M(n + 1, vector<int>(n + 1, 0));

        for (int i = 2; i <= n; i += 2)
        {
            for (int j = 1; j <= n; j += 2)
            {
                M[i][j] = cur;
                a[cur]--;
                while (a[cur] == 0 && cur != (mi==1?k1:mi-1))
                {
                    cur++;
                    if (cur == k1 + 1)
                        cur = cur % k1;
                }
                if (a[cur] == 0 && cur == (mi == 1 ? k1 : mi - 1))
                    cur = 0;
            }
        }
        for (int i = 1; i <= n; i += 2)
        {
            for (int j = 1; j <= n; j += 2)
            {
                M[i][j] = cur;
                a[cur]--;
                while (a[cur] == 0 && cur != (mi == 1 ? k1 : mi - 1))
                {
                    cur++;
                    if (cur == k1+ 1)
                        cur = cur % k1;
                }
                if (a[cur] == 0 && cur == (mi == 1 ? k1 : mi - 1))
                    cur = 0;
            }
        }
        for (int i = 1; i <= n; i += 2)
        {
            for (int j = 2; j <= n; j += 2)
            {
                M[i][j] = cur;
                a[cur]--;
                while (a[cur] == 0 && cur != (mi == 1 ? k1 : mi - 1))
                {
                    cur++;
                    if (cur == k1 + 1)
                        cur = cur % k1;
                }
                if (a[cur] == 0 && cur == (mi == 1 ? k1 : mi - 1))
                    cur = 0;
            }
        }
        // cout<<cur<<" "<<a[cur]<<"\n";
        

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cout << M[i][j] << " ";
            cout << "\n";
        }
    }
}