합창단

마우드(Maud)는 합창단의 지휘자이며 4성부 노래로 이루어진 공연을 준비하고 있다. 4성부 노래에서는 작곡가가 서로 다른 네 개의 성부를 쓰고, 각 단원은 그중 하나를 부른다. 높은 성부부터 낮은 성부까지 차례로 소프라노(Soprano), 알토(Alto), 테너(Tenor), 베이스(Bass) 성부이며, 각각 S, A, T, B로 줄여 쓴다.

이상적으로는 모든 단원이 자신의 목소리에 가장 잘 맞는 성부를 부르지만, 실제 합창단은 더 유연하다. 어떤 단원은 두 개 이상의 성부를 부를 수 있다. 소프라노는 항상 소프라노 성부를 부른다. 어떤 단원은 알토 성부와 테너 성부 중 하나를 부를 수 있고, 또 어떤 단원은 테너 성부와 베이스 성부 중 하나를 부를 수 있다. 따라서 한 단원이 어떤 노래에서는 알토를, 다른 노래에서는 테너를 부를 수 있고, 또는 어떤 노래에서는 테너를, 다른 노래에서는 베이스를 부를 수 있다.

마우드는 각 노래마다 어떤 단원이 어떤 성부를 부를지 이미 정해 두었다. 합창단은 한 줄로 서서 공연한다. 같은 성부를 부르는 단원들은 서로 이웃해 서며, 왼쪽에서 오른쪽으로 소프라노, 알토, 테너, 베이스 순서로 늘어선다. 같은 성부 안에서는 단원들이 어떤 순서로 서도 된다.

한 단원이 노래마다 다른 성부를 부를 수 있기 때문에, 노래 사이에 단원들은 자리를 바꿔야 하며 이는 번거로우므로 되도록 피해야 한다. 줄이 새로 배치될 때, 서 있는 사람이 바뀌는 자리마다 교체가 한 번씩 센다. 예를 들어 1번 자리에 서 있던 단원이 5번 자리로 이동하면, 2, 3, 4, 5번 자리의 단원들이 각각 한 칸씩 밀려서 1번부터 5번까지 다섯 자리 모두 서 있는 사람이 바뀌므로, 이는 교체 5번으로 센다.

주어진 두 노래 사이에서는 각 성부 안의 단원들을 그 두 노래 사이의 변화가 가장 작아지도록 원하는 순서로 세울 수 있다. 그러면 두 노래 사이의 교체 횟수는, 합창단이 한 노래에서 다른 노래로 곧바로 바뀔 때 서 있는 사람이 바뀌는 자리 수의 가능한 최솟값이다.

마우드는 노래를 어떤 순서로도 공연할 수 있다. 전체 교체 횟수는, 정한 순서에서 서로 이웃한 모든 노래 쌍에 대해 그 두 노래 사이의 교체 횟수를 더한 값이다. 이 합이 가장 작아지도록 노래의 순서를 정하고, 그 최소 합을 구하여라.

첫째 줄에 정수 $n$ ($0 < n \le 100$), 즉 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 한 줄에 두 양의 정수 $m$ ($m \le 6$), 즉 노래의 수와 $s$ ($s \le 20$), 즉 단원의 수가 주어진다.
• 이어서 $m$개의 줄에 각 노래가 하나씩 주어진다. 단원은 $1$번부터 $s$번까지 번호가 매겨져 있다. 각 노래는 문자 S, A, T, B로 이루어진 길이 $s$의 문자열로 표현되며, $i$번째 문자는 그 노래에서 $i$번 단원이 부르는 성부이다. 예를 들어 문자열 BBSAT는 1번과 2번 단원이 베이스 성부를, 3번 단원이 소프라노 성부를, 4번 단원이 알토 성부를, 5번 단원이 테너 성부를 부른다는 뜻이다. 모든 노래는 네 성부를 모두 사용한다.

각 테스트 케이스마다, 공연하는 노래의 순서와 단원들의 배치를 이 값이 가장 작아지도록 정했을 때 전체 교체 횟수의 최솟값을 한 줄에 출력한다.