11961 - DNA

DNA有四種鹼基：A, C, G, T。給定長度為N的DNA序列，我們說此DNA的「第K突變(K-th mutation)」表示此DNA可藉由原始DNA改變K個元素來得到，例如GAT為GGT的第一突變，為TTT的第二突變。

給定一原始的DNA序列，及最大的突變數K，請你列出所有可能的組合(包含第0~K突變)。

INPUT

輸入的第一列有一整數T(T <= 50)表示測試資料的組數，每組資料兩列，第一列有兩個整數N(N <= 10)，K(K <= 5)，第二列為長度N的原始DNA序列。

OUTPUT

請每組測試資料輸出所有組合的總數，並以字典順序由小到大輸出所有組合。

SAMPLE INPUT

1
3 1
AAA

SAMPLE OUTPUT

10
AAA
AAC
AAG
AAT
ACA
AGA
ATA
CAA
GAA
TAA

---

原文出處