学生们太淘气了：他们一直在互相分享代码！你手头有他们所有提交的代码列表，你想手动检查一些代码对是否存在抄袭行为。

每个提交都是一个由大写拉丁字母组成的字符串。设 $k$ 为一个整数。如果字符串 $s$ 可以通过将 $t$ 中一个长度不超过 $k$ 的（可能为空的）子串替换为另一个长度不超过 $k$ 的（可能为空的）字符串得到（反之亦然），则称提交对 $\{s, t\}$ 是 $k$-可疑的。回想一下，子串是字符串中一段连续的片段。

对于给定的整数 $k$，有多少对提交是 $k$-可疑的？

输入格式

输入的第一行包含测试用例的数量 $Z$ ($1 \le Z \le 90\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含整数 $n$ 和 $k$ ($1 \le n \le 100\,000, 1 \le k \le 1\,000\,000$)，分别表示提交的数量和整数参数。接下来的 $n$ 行描述了这些提交。第 $i$ 行包含一个由大写拉丁字母组成的字符串 $s_i$，即第 $i$ 个提交。保证所有提交互不相同，即没有两个字符串是相等的。

单个测试用例中所有提交的总长度不超过 $1\,000\,000$。所有测试用例中 $n$ 的总和不超过 $200\,000$。所有测试用例中所有提交的总长度不超过 $2\,000\,000$。

输出格式

对于每个测试用例，输出一个整数，表示 $k$-可疑的提交对数量。

样例

输入 1

1
4 2
SUFFIXTREE
SUSIXTREE
SUFFIXTREAP
SUFFIXARRAY

输出 1

2

说明

样例中只有两对 2-可疑的字符串（被替换的子串已加粗）：(SUFFIXTREE, SUSIXTREE) 和 (SUFFIXTREE, SUFFIXTREAP)。