유사 라임 게임

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

먼저, 영문 대문자로만 구성된 길이가 $L$인 서로 다른 단어 $n$개를 종이에 적는다: 편의상 $W\_1, W\_2, \dots W\_n$을 $n$개의 단어라 하자.

어떤 한 쌍의 단어 $W\_i$와 $W\_j$를 비교했을 때 최대 공통 접미사의 길이가 $F$이상이면 두 단어는 "유사 라임"을 이룬다고 정의한다. 이러한 단어 쌍을 "유사 라임 쌍"이라 부르자.

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

예를 들어 $n = 4$, $L = 4$일때, $4$개의 단어가 다음과 같다고 하자: $W\_1 =$ "WALK", $W\_2 =$ "TALK", $W\_3 =$ "MILK", $W\_4 =$ "BULK".

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

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

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

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

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

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

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