HAHA.

Khi chat chit vui vẻ, anh em chiến hữu thường hay gõ HAHA để thể hiện sự sảng khoái. Đôi khi cũng có thể gõ HAHAAAAA chẳng hạn cho thêm phần nhấn mạnh. Giả sử một xâu ký tự được coi là HAHA nếu thỏa mãn các điều kiện: Ký tự đầu tiên phải là chữ H, ký tự cuối cùng phải là chữ A. Không có hai chữ H nào liền nhau. Hãy liệt kê tất cả các xâu ký tự HAHA theo thứ tự từ điển.

Input Format

Dòng đầu ghi số bộ test T (không quá 10). Mỗi bộ test ghi độ dài N (2 <= N < 16).

Constraints

.

Output Format

Với mỗi bộ test, ghi ra tất cả các xâu HAHA tìm được theo thứ tự từ điển, mỗi xâu viết trên một dòng.

Ví dụ:

Dữ liệu vào

2
2
4

Dữ liệu ra

HA
HAAA
HAHA