SP21861 STRNGSLV - I Love Strings

Sacchi 和 Maurya 是字符串的狂热爱好者。他们热衷于解答有关字符串的问题。于是，天资聪颖的 Priyun 决定给他们出一道挑战。Priyun 提供了一个只包含小写字母的字符串 $S$。在他的定义中，某些字母是「Nice」，而其余部分是「Eww」。Priyun 对「Eww」字符有一个容忍阈值——最多可以容忍 $X$ 个「Eww」字母的子串。 现在 Priyun 想知道，对于这个给定的字符串，他能容认的不同子串有多少种。就连聪明的 Sacchi 和 Maurya 也觉得这道题有些棘手，所以来帮帮他们吧。

输入文件包含若干个测试用例，总共有 $T$ 组（$1 \le T \le 10$）。 每组测试用例的第一行是字符串 $S$，长度不超过 2000，字符串只由小写字母构成。 接下来一行是整数 $P$（$0 \le P \le 26$），表示「Nice」字母的数量。 接下来的 $P$ 行中每行包含一个「Nice」字母。这些字母都是唯一的，并且在小写字母范围内 [a, z]。 最后一行是一个整数 $X$，表示 Priyun 对「Eww」字母的容忍度。

对于每个测试用例，输出一个整数，表示 Priyun 能接受的不同子串数量。 **本翻译由 AI 自动生成**