유사 라임 게임

Alice는 영어 단어를 조합해 라임(rhyme)을 만드는 단어 게임을 즐긴다. Bob도 라임을 만들고 싶어 하지만 아직 어려서 단어를 잘 모르기 때문에, Alice가 "유사 라임 게임"을 제안했다.

먼저 영문 대문자로만 이루어진 길이 $L$인 서로 다른 단어 $n$개를 종이에 적는다. 편의상 이 단어들을 $W_1, W_2, \dots, W_n$이라 하자.

두 단어 $W_i$와 $W_j$의 최대 공통 접미사의 길이가 $F$ 이상이면 두 단어가 "유사 라임"을 이룬다고 정의한다. 이런 단어 쌍을 "유사 라임 쌍"이라 부른다.

"유사 라임 게임"은 주어진 단어들로 최대한 많은 "유사 라임 쌍"을 만드는 게임이다. 단, 한 단어는 최대 하나의 유사 라임 쌍에만 속할 수 있다.

예를 들어 $n = 4$, $L = 4$이고 네 단어가 $W_1 =$ "WALK", $W_2 =$ "TALK", $W_3 =$ "MILK", $W_4 =$ "BULK"라 하자.

• $F \le 2$라면 아무렇게나 두 쌍으로 묶어도 유사 라임 쌍이 되므로 $2$개의 쌍을 찾을 수 있다. 예를 들면 ("WALK", "BULK"), ("TALK", "MILK")가 있다.
• $F = 3$이라면 ("WALK", "TALK")를 묶어 유사 라임 쌍 하나를 만들 수 있지만, $2$개 이상을 만들 방법은 없다.
• $F \ge 4$라면 유사 라임 쌍을 만들 방법은 없다.

입력으로 $F$와 길이 $L$인 $n$개의 단어가 주어졌을 때, Bob이 만들 수 있는 "유사 라임 쌍"의 최대 개수를 구해보자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 입력은 두 줄에 걸쳐 주어진다. 첫 줄에 $n$, $L$, $F$가 공백으로 구분되어 주어진다. 둘째 줄에 영문 대문자로만 이루어진 길이 $L$인 문자열 $n$개 $W_1, W_2, \dots, W_n$이 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• $1 \le T \le 10$
• $1 \le F \le L \le 10$
• $2 \le n \le 500$
• 각 문자열 $W_i$는 알파벳 대문자로만 이루어져 있다.
• 각 테스트 케이스에 주어지는 $n$개의 문자열은 중복되지 않는다.

최대 공통 접미사: 두 문자열의 공통 접미사(common suffix) 중 길이가 가장 긴 것을 말한다.