SP177 ABWORDS - AB-words

由小写字母 a 和 b 组成的序列（包括空序列）称为 ab-词。如果 $X = [x_1, \ldots, x_n]$ 是一个 ab-词，并且 $i, j$ 是满足 $1 \le i \le j \le n$ 的整数，则 $X[i..j]$ 表示 $X$ 中从第 $i$ 个到第 $j$ 个字母的子序列。一个 ab-词 $X = [x_1, \ldots, x_n]$ 被称为“好的”如果具有以下两个性质：一是字母 a 和 b 的数量相等；二是对于所有 $i = 1, \ldots, n$，子序列 $X[1..i]$ 中字母 a 的数量不少于字母 b。 我们定义“好 ab-词”之间的相似性，规则如下： - 所有空 ab-词（即没有字母的词）彼此相似。 - 两个非空的好 ab-词 $X = [x_1, \ldots, x_n]$ 和 $Y = [y_1, \ldots, y_m]$ 如果长度相等（即 $n = m$），并满足下述任一条件，则为相似： 1. $x_1 = y_1$ 且 $x_n = y_n$，并且中间部分 $X[2..n-1]$ 和 $Y[2..n-1]$ 是相似的好 ab-词。 2. 存在一个 $i$，使得 $1 \le i \le n$： 1. $X[1..i]$ 和 $X[i+1..n]$ 都是好 ab-词，并且 $Y[1..i]$ 和 $Y[i+1..n]$ 也都是好 ab-词，同时 $X[1..i]$ 与 $Y[1..i]$ 相似，$X[i+1..n]$ 与 $Y[i+1..n]$ 相似； 2. 或者 $Y[1..n-i]$ 和 $Y[n-i+1..n]$ 都是好 ab-词，并且 $X[1..i]$ 与 $Y[n-i+1..n]$ 相似，$X[i+1..n]$ 与 $Y[1..n-i]$ 相似。

第一行输入一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例，每个用例之间以一个空行分隔。 每个测试用例的第一行包含一个整数 $n$，表示集合 $S$ 中元素的数量，$1 \le n \le 1000$。接下来的 $n$ 行，每行包含集合 $S$ 的一个元素，即一个好的 ab-词。这些词中的字母是连续的，中间没有空格，长度在 $[1, 200]$ 范围内。

对于每个测试用例，输出一行，包含一个整数，表示集合 $S$ 的多样性级别。 **本翻译由 AI 自动生成**