Choir

Maud is the choirmaster of a choir and is preparing a program of four-part songs. In a four-part song the composer writes four different parts, and each singer sings one of them. From the highest part to the lowest they are the Soprano part, the Alto part, the Tenor part, and the Bass part, abbreviated S, A, T, and B.

Ideally every singer sings the part that best fits their voice, but real choirs are more flexible: some singers can sing more than one part. Sopranos always sing the soprano part. Some singers can sing either the alto part or the tenor part, and some can sing either the tenor part or the bass part. So a singer may sing alto in one song and tenor in another, or tenor in one song and bass in another.

For every song Maud has already decided which singer sings which part. The choir performs standing in a single line. Singers who sing the same part stand together, and from left to right the parts appear in the order soprano, alto, tenor, bass. Within a single part the singers may stand in any order.

Because a singer may sing a different part in different songs, the singers have to change places between songs, which is distracting and should be avoided. When the line is rearranged, one replacement is counted for every position whose occupant changes. For example, if the singer standing at position 1 moves to position 5, the singers at positions 2, 3, 4, and 5 each shift one place, so all five positions 1 through 5 receive a new occupant — that counts as 5 replacements.

Between two given songs, the singers within each part may be lined up in whatever order makes the change between those two songs as small as possible. The number of replacements between the two songs is then the smallest possible number of positions whose occupant changes when the choir goes directly from one of the songs to the other.

Maud may perform the songs in any order. The total number of replacements is the sum, over every pair of consecutive songs in the chosen order, of the number of replacements between those two songs. Order the songs so that this total is as small as possible, and report that minimum total.

The first line contains an integer $n$ ($0 < n \le 100$), the number of test cases. Each test case is given as follows:

• A line with two positive integers $m$ ($m \le 6$), the number of songs, and $s$ ($s \le 20$), the number of singers.
• Then $m$ lines, one for each song. The singers are numbered $1$ to $s$. A song is described by a string of length $s$ over the characters S, A, T, B; the $i$-th character is the part sung by singer $i$ in that song. For example, the string BBSAT means that singers one and two sing the bass part, singer three sings the soprano part, singer four the alto part, and singer five the tenor part. Every song uses all four parts.

For each test case, print a single line with the minimum possible total number of replacements, assuming the order of the songs and the placement of the singers are chosen to make this total as small as possible.