AP là một người siêu thông minh nhưng bị mắc bệnh ám ảnh cưỡng chế. Bất kỳ dữ liệu gì anh cũng phải mã hóa nó thành dạng chuỗi ký tự. Lần này AP có một số ~n~ và dãy ~a_1, a_2, ..., a_n~, anh muốn mã hóa nó thành chuỗi ký tự chỉ gồm các chữ cái in thường. Chuỗi gồm ~n~ đoạn, đoạn thứ ~i~ có độ dài ~a_i~ và phải thỏa mãn điều kiện:

• Nếu ~i~ là số lẻ thì các ký tự trong đoạn thứ ~i~ phải thỏa mãn ký tự đứng sau có thứ tự từ điển bé hơn ký tự đứng trước. Lưu ý rằng ký tự đầu tiên của đoạn ~i~ này có thứ tự từ điển bé hơn ký tự cuối cùng của đoạn ~i-1~.

• Nếu ~i~ là số chẵn thì các ký tự trong đoạn thứ ~i~ phải thỏa mãn ký tự đứng sau có thứ tự từ điển lớn hơn ký tự đứng trước. Lưu ý rằng ký tự đầu tiên của đoạn ~i~ này có thứ tự từ điển lớn hơn ký tự cuối cùng của đoạn ~i-1~. (với ~i>1~)

• Ký tự đầu tiên của đoạn ~1~ luôn là ký tự '~z~'.

Hãy tìm chuỗi ký tự thỏa mãn đề bài.

Input

• Dòng đầu tiên chứa số ~Q~ là số lượng truy vấn.
• ~Q~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~n~ là số đoạn trong chuỗi ký tự và dãy ~a_1, a_2, a_3, ..., a_n~ với ~a_i~ là độ dài đoạn thứ ~i~. ~(1 \le a_i \le 26)~

Output

• Ứng với mỗi truy vấn, in ra chuỗi ký tự thỏa mãn đề bài. Mỗi truy vấn in ra trên một dòng.
• Trong trường hợp có nhiều đáp án, in ra chuỗi ký tự có thứ tự từ điển bé nhất. Ngược lại nếu không tìm được chuỗi ký tự thỏa mãn in ra ~-1~.

Sample Input

2
2
26 3
3
2 3 3

Sample Output

zyxwvutsrqponmlkjihgfedcbabcd
zabcdcba

Subtask

• ~30\%~ số test có ~1 \le Q \le 10, 1 \le n \le 2~
• ~70\%~ số test tiếp theo có ~1 \le Q \le 50, 1 \le n \le 2*10^4~