Time Limit: 1 sec
Memory Limit: 32 MB
Alan was comleting his internship at chemistry faculty. At the beginning internship seemed to be easy. However one day dean of the faculty of chemistry have given John a certain task to solve. Alan was asked to perform DNA and protein modelling using free OpenEye software kit.
As Alan like all programmers is very lazy, he would like to use computer as much as possible. So now he needs to generate all possible DNA mutations and share them to OpenEye software. Alan decided to use computer not only for OpenEye software but also for mutation generation purpose.
At the beginning of the internship Alan studying a little bit of chemistry science, so he knows that DNA consisting of 4 elements (Adenine, Guanine, Cytosine, and Thymine) and can be described as a sequence of four letters (for example: GATCC). The K-th mutation of inital DNA sequence of length N is called a sequence that can be produced by replacing ((possibly to the same nucleotide)) exactly K elements of the sequence (for example GAT is the 1-st mutation of GGT and the 2-nd mutation of TTT).
Alan is given initial DNA sequence and maximal power of its possible mutataion. Can you produce all possible mutated DNA sequences for Alan?
The number of tests T (T ≤ 50) is given on the first line. Each test case if described by two lines: one the first is number N (N ≤ 10 ) and K (K ≤ 5), on the second line is written DNA sequence of length N.
For each test case print M — the number of different DNA mutations. After this print all mutated DNA sequences in alphabetical order. Refer to the sample output for details.
1 3 1 AAA
10 AAA AAC AAG AAT ACA AGA ATA CAA GAA TAA