Problem: The length of the longest common prefix of two strings s = s_1 s_2 … s_n and t = t_1 t_2 … t_m is defined as the maximum integer k (0 ≤ k ≤ min(n,m)) such that s_1 s_2 … s_k equals t_1 t_2 … t_k.

Koa the Koala initially has n+1 strings s_1, s_2, ..., s_{n+1}.

For each i (1 ≤ i ≤ n) she calculated a_i — the length of the longest common prefix of s_i and s_{i+1}.

Several days later Koa found these numbers, but she couldn't remember the strings.

So Koa would like to find some strings s_1, s_2, ..., s_{n+1} which would have generated numbers a_1, a_2, ..., a_n. Can you help her?

If there are many answers print any. We can show that answer always exists for the given constraints. 

Input

Each test contains multiple test cases. The first line contains t (1 ≤ t ≤ 100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100) — the number of elements in the list a.

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 50) — the elements of a.

It is guaranteed that the sum of n over all test cases does not exceed 100.

Output

For each test case:

Output n+1 lines. In the i-th line print string s_i (1 ≤ |s_i| ≤ 200), consisting of lowercase Latin letters. Length of the longest common prefix of strings s_i and s_{i+1} has to be equal to a_i.

If there are many answers print any. We can show that answer always exists for the given constraints.

Example

Input


4
4
1 2 4 2
2
5 3
3
1 3 1
3
0 0 0


Output


aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems

Note

In the 1-st test case one of the possible answers is s = [aeren, ari, arousal, around, ari].

Lengths of longest common prefixes are:

  * Between \color{red}{a}eren and \color{red}{a}ri → 1 
  * Between \color{red}{ar}i and \color{red}{ar}ousal → 2 
  * Between \color{red}{arou}sal and \color{red}{arou}nd → 4 
  * Between \color{red}{ar}ound and \color{red}{ar}i → 2 

Solution (in JAVA):

Solution:
/**
 * https://codeforces.com/contest/1384/problem/A
 */

import java.io.*;
import java.util.*;
import java.lang.*;

public class CommonPrefixes {
	public static final int size = 101;
	public static void main(String[] args) throws IOException {
		FastReader in = new FastReader();
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		int t = in.nextInt();
		while (t-- > 0) {
			int n = in.nextInt();
			int[] a = in.nextIntArray(n);

			char[][] ans = new char[n + 1][size];
			// init
			for (int i = 0; i < size; i++) {
				ans[0][i] = 'a';
			}

			for (int i = 0; i < n; i++) {
				char temp = ans[i][a[i]];
				temp = temp == 'z' ? 'a' : (char)(temp + 1);
				
				for (int j = 0; j < size; j++) {
					ans[i + 1][j] = ans[i][j];
				}
				ans[i + 1][a[i]] = temp;
			}

			for (int i = 0; i < n + 1; i++) {
				for (int j = 0; j < size; j++) {
					out.print(ans[i][j]);
				}
				out.println();
			}
		}
        out.close();
	}

	static String init(int n) {
		String result = "";
		for (int i = 0; i < n; i++) {
			result += (char) (i + 'a');
		}
		return result;
	}
}	

/*~~~~~~~~~~~~~~~~~    UTILITY METHODS    ~~~~~~~~~~~~~~~~~*/
class Utilities {
	static long mod = (long) (1e9 + 7);

    static void debug(Object...args) {
		System.out.println(Arrays.deepToString(args));
	}

	static class Pair {
        int x;
        int y;

        public Pair (int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int hashCode() {
            final int PRIME = 59;
            int result = 1;
            result = (result * PRIME) + this.x;
            result = (result * PRIME) + this.y;
            return result;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair= (Pair) o;
            return x == pair.x && y == pair.y;
        }
        @Override
        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }
	
	static void factorial(long[] fact, int n) {
		fact[0] = 1;
		for(int i = 1; i < n; i++) {
			fact[i] = (i * fact[i-1]) % mod;
		}
	}
	
	static int lower_bound(int[] a, int low, int high, int key) {
	    while (low < high) {
	        int mid = low + ((high - low) >> 1);
	        if (a[mid] >= key) {
	            high = mid;
	        }
	        else {
	            low = mid + 1;
	        }
	    }
	    return low;
	}

	static int upper_bound(int[] a, int low, int high, int key) {
	    while (low < high) {
	        int mid = low + ((high - low) >> 1);
	        if (a[mid] <= key) {
	            low = mid + 1;
	        }
	        else {
	            high = mid;
	        }
	    }
	    return low;
	}

	// returns (x ^ y) % mod
	static long power(long x, long y, long mod) {
		if (y == 0) return 1 % mod;
		if (y == 1) return x % mod;
		long res = 1;
		x = x % mod;
		while (y > 0) {
			if ((y & 1) == 1) {
				res = (res * x) % mod;
			}
			y = y >> 1;
			x = (x * x) % mod;
		}
		return res;
	}
	// returns (1/a) % (10^9 + 7)
	static long modInv(long x, long mod) {
		return power(x, mod - 2, mod);
	}

	// returns value of nCr
	static long C(long[] fact, long n, long r, long mod) {
		long result = (fact[(int) n] * modInv(fact[(int) r], mod)) % mod;
		result = (result * modInv(fact[(int) (n - r)], mod)) % mod;
		return result;
	}

	static long gcd(long a, long b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	// Finding Smallest Prime Factor has similar implementation as sieve
	static void sieve(boolean[] prime, int n) {
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (prime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
}

/*~~~~~~~~~~~~~~~~~    FAST INPUT METHODS    ~~~~~~~~~~~~~~~~~*/
class FastReader {
    final private static int BUFFER_SIZE = 1 << 16;
	private static DataInputStream din;
	private static byte[] buffer;
	private static int bufferPointer = 0, bytesRead = 0;
 
	public FastReader () {
		din = new DataInputStream(System.in);
		buffer = new byte[BUFFER_SIZE];
	}
	static String nextLine() throws IOException {
		int c = read();
		while(isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while(!isEndOfLine(c));
		return res.toString();
	}
	static String next() throws IOException {
		int c = read();
		while(isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while(!isSpaceChar(c));
		return res.toString();
	}
	static int nextInt() throws IOException {
		int ret = 0;
		byte c = read();
		while(c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if(neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while((c = read()) >= '0' && c <= '9');
		if (neg)
			return -ret;
		return ret;
	}
	static int[] nextIntArray(int n) throws IOException {
		int a[] = new int[n];
		for(int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}
	static int[][] next2dIntArray(int n, int m) throws IOException {
		int a[][] = new int[n][m];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				a[i][j] = nextInt();
		return a;
	}
	static char nextChar() throws IOException {
		return next().charAt(0);
	}
	static long nextLong() throws IOException {
		long ret = 0;
		byte c = read();
		while(c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if(neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while((c = read()) >= '0' && c <= '9');
		if (neg)
			return -ret;
		return ret;
	}
	static double nextDouble() throws IOException {
		double ret = 0, div = 1;
		byte c = read();
		while(c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if(neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while((c = read()) >= '0' && c <= '9');
		if (c == '.') {
			while((c = read()) >= '0' && c <= '9') {
				ret += (c - '0') / (div *= 10);
			}
		}
		if(neg)
			return -ret;
		return ret;
	}
	static void fillBuffer() throws IOException {
		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
		if(bytesRead == -1)
			buffer[0] = -1;
	}
	static byte read() throws IOException {
		if(bufferPointer == bytesRead)
			fillBuffer();
		return buffer[bufferPointer++];
	}
	static void closeReader() throws IOException {
		if(din == null)
			return;
		din.close();
	}
	static boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}