The students have been naughty: they have been sharing codes between each other! You have the list of all their submissions, and you want to examine some pairs of codes manually for plagiarism.
Each submission is a string consisting of uppercase Latin characters. Let $$$k$$$ be an integer. A pair of submissions $$$\{s, t\}$$$ is called $$$k$$$-suspicious if $$$s$$$ can be obtained from $$$t$$$ by replacing a (possibly empty) substring of length at most $$$k$$$ with another (possibly empty) string of length at most $$$k$$$ (and vice versa). Recall that a substring is a connected fragment of a string.
For a given integer $$$k$$$, how many pairs of submissions are $$$k$$$-suspicious?
The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 90\,000$$$). The descriptions of the test cases follow.
The first line of a test case contains integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1 \leq k \leq 1\,000\,000$$$) – the number of submissions and an integer parameter respectively. The following $$$n$$$ lines describe the submissions. The $$$i$$$-th line contains a string $$$s_i$$$ consisting of uppercase Latin characters – the $$$i$$$-th submission. It is guaranteed that submissions are pairwise different, i.e., no two strings are equal.
The total length of all submissions in a single test case does not exceed $$$1\,000\,000$$$. The sum of $$$n$$$ in all test cases does not exceed $$$200\,000$$$. The total length of all submissions in all test cases does not exceed $$$2\,000\,000$$$.
For each test case, print a single integer denoting the number of $$$k$$$-suspicious pairs of submissions.
1 4 2 SUFFIXTREE SUSIXTREE SUFFIXTREAP SUFFIXARRAY
2
There are only two pairs of $$$2$$$-suspicious strings in the sample (the replaced substrings are marked bold): (SUFFIXTREE, SUSIXTREE) and (SUFFIXTREE, SUFFIXTREAP).
| Название |
|---|


