3466번 - Choir 다국어

Maud is the choirmaster of a choir, and she is preparing a performance of some four-part songs. Four-part means that not every singer sings the same notes, the composer wrote four different parts, and the parts are divided among the singers. The highest part is called the Soprano part, the second highest part is the Alto part, which is followed by the Tenor part, while the lowest part is the Bass part. These different parts are usually denoted (abbreviated) S, A, T, B.

In a perfect world, every singer always sings the part that fits him or her best: women with a high voice (sopranos) sing the soprano part, women with a low voice (altos) sing the alto-part, and the same goes for the male voices (tenor and bass). Of course reality is different. In a way reality is better than perfect. Some singers are not strictly bass or tenor, but are able to sing both tenor and bass parts (not at the same time, though). This is quite helpful because genuine tenors are rare. In the same way some women are able to sing both alto and tenor parts. These multi-talents are rare, however. In Maud's choir only four women are able to sing both alto and tenor, and only three men are able to sing both tenor and bass.

For every song, Maud has decided which singer sings which part. Because of a lack of tenors, some singers sing alto in one song, and tenor in another. Others sometimes sing tenor, and sometimes bass. In this choir sopranos always sing the soprano part. The choir is quite small, so they sing standing in a single line (actually half a circle). Singers singing the same part are standing together: at the leftmost (seen from the choirmaster) the singers singing the soprano part, then the singers singing the alto part, the tenor part and at the rightmost hand the singers singing the bass part. Because singers sometimes sing a different voice in a different song, they have to change places between the songs. This is disturbing, and should be avoided as much as possible. Here is the problem: order the songs in such a way that the number of replacements during the program is minimal. If between two songs two singers have to change place, it counts as two replacements. If the singer at position 1 moves to position 5, four other singers on position 2 upto 4 have to shift, making up for a total of 5 replacements.

• The first line of input consists of the integer number n (0 < n ≤ 100), the number of test cases;
• Then, for each test case:
  • A line containing two positive integers m ≤ 6 (the number of songs) and s ≤ 20 (the number of singers);
  • m lines describe for each song the division of the parts over the singers. For simplicity the singers are numbered 1 to s. The division is then denoted as a string of length s. The string BBSAT indicates that singer one sings the bass part, as does singer two. Singer three sings the soprano-part, and so on. Each song has exactly four parts.

For each test case your program should print the total number of replacements during the performance if the program order and the placement of the singers is chosen such as to minimize the number of replacements. Follow the format of the sample.