霉球研究
题号：NC229816
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

传说中，垢尝是一种洒扫庭除的妖怪，他喜欢研究霉球。

垢尝所研究的每一个霉球可以看做一串仅包含英文小写字母的非空字符串。现在，他有一个代表字符串 s 的大型霉球，以及 n 个代表字符串 的霉球，他希望用这 n 个霉球拼接出大型霉球 s。

具体来说，令 s' 为答案串，且一开始为空串。接下来垢尝可以进行若干轮操作：每一轮中，垢尝将从 里任选一个串 t，并以任意顺序执行零次或任意多次下列的操作得到 t'，接着将 t' 接在 s' 的末尾，结束这一轮。操作包括：

  • 移除 t 开头的一个字符
  • 移除 t 末尾的一个字符
  • 往 t 开头追加一个任意字符
  • 往 t 末尾追加一个任意字符

四种操作的单次执行代价都是 1。例如，垢尝可以在一轮中对代表字符串 nowcoder 使用 3 次操作删除开头的三个字符、使用 1 次操作 4 往末尾追加一个字符 s，并获得 coders 这个新字符串。此时的执行代价为 。需要注意的是，每轮操作中所选择的串 t，仍然能在后续的轮次中被选择。

显然，一定存在至少一种方案使得若干轮操作后答案串 。垢尝希望用最小的执行代价合成这个大型煤球，请你告诉他这个代价。

输入描述:

本题有多组输入数据。

第一行为一个正整数 T ()，表示数据组数。接下来的每一组数据中包含若干行。

每组数据的第一行为一个字符串 s ()，含义见题目描述。

接下来的一行为一个整数 n ()，含义见题目描述。

接下来的 n 行，每行为一个字符串，依次表示 。保证对 ，都有 。

对于所有数据，保证所有输入字符串的串长之和不超过 ，且字符串仅包含小写英文字母。

输出描述:

对于每组数据输出一行一个整数，表示垢尝的最小执行代价。
示例1

输入

复制 
2
nowcoder
3
own
nowhere
coding
nowcoder
1
coding

输出

复制 
7
8

说明

对于第一组数据，垢尝的操作如下：

1. 对字符串 own 使用 1 次操作 2 变成 ow，使用 1 次操作 3 往开头追加字符 n 变成 now；

2. 对字符串 coding 使用 3 次操作 2 变成 cod，使用 2 次操作 4 往末尾追加字符 e 和 r 变成 coder；

3. 拼接 now 与 coder 得到 nowcoder。

总执行代价为 1 + 1 + 3 + 2 = 7。