Similar Rhyme Game

Alice enjoys a word game in which she combines English words to make rhymes. Bob also wants to make rhymes, but he is young and does not know many words, so Alice proposes the "Similar Rhyme Game."

First, write $n$ distinct words of length $L$ consisting only of uppercase English letters on paper. For convenience, call these words $W_1, W_2, \dots, W_n$.

When comparing a pair of words $W_i$ and $W_j$, if the length of their longest common suffix is at least $F$, the two words are said to form a "similar rhyme." Such a pair of words is called a "similar rhyme pair."

The "Similar Rhyme Game" is a game of forming as many "similar rhyme pairs" as possible from the given words. Each word may belong to at most one similar rhyme pair.

For example, let $n = 4$ and $L = 4$, with the four words $W_1 =$ "WALK", $W_2 =$ "TALK", $W_3 =$ "MILK", $W_4 =$ "BULK".

• If $F \le 2$, pairing the words into any two pairs gives similar rhyme pairs, so $2$ pairs can be found. For example, ("WALK", "BULK") and ("TALK", "MILK").
• If $F = 3$, pairing ("WALK", "TALK") forms one similar rhyme pair, but there is no way to form $2$ or more.
• If $F \ge 4$, there is no way to form a similar rhyme pair.

Given $F$ and $n$ words of length $L$ as input, find the maximum number of "similar rhyme pairs" Bob can form.

The first line gives the number of test cases $T$.

The input for each test case is given over two lines. The first line gives $n$, $L$, and $F$, separated by spaces. The second line gives $n$ strings $W_1, W_2, \dots, W_n$ of length $L$ consisting only of uppercase English letters, separated by spaces.

For each test case, print the answer on its own line.

• $1 \le T \le 10$
• $1 \le F \le L \le 10$
• $2 \le n \le 500$
• Each string $W_i$ consists only of uppercase English letters.
• The $n$ strings given in each test case are distinct.

Longest common suffix: the longest common suffix of two strings, that is, the common suffix with the greatest length.