给出 $n$ 个单词 $(n \le 2 \times 10^4)$ ，每个单词由一些小写字母组成。现在这些单词按照输入的顺序给定，每个单词还有一个权值，当然可能出现某个单词出现了两次，即两个串完全一样但是多次出现，权值还可能不同。

你可以将这 $n$ 个单词删掉一些之后，如果剩下的单词满足按照原本输入的顺序排列，上面一个是下面一个的子串，这种删除方法是合法的，求在所有合法的删除方案中剩下的单词的权值和最大是多少？

输入第一行为数据组数，每组数据第一行为 $n$ 的大小。接下来 $n$ 行，每行一个单词。保证输入的单词总长度不超过 $3 \times 10^6$。

给出 $n$ 个单词 $(n \le 2 \times 10^4)$ ，每个单词由一些小写字母组成。现在这些单词按照输入的顺序给定，每个单词还有一个权值，当然可能出现某个单词出现了两次，即两个串完全一样但是多次出现，权值还可能不同。

你可以将这 $n$ 个单词删掉一些之后，如果剩下的单词满足按照原本输入的顺序排列，上面一个是下面一个的子串，这种删除方法是合法的，求在所有合法的删除方案中剩下的单词的权值和最大是多少？

输入第一行为数据组数，每组数据第一行为 $n$ 的大小。接下来 $n$ 行，每行一个单词。保证输入的单词总长度不超过 $3 \times 10^6$。