题目描述

对于字符串 $s$，用 $s_{l\dots r}$ 代表 $s$ 的第 $l$ 个字符到第 $r$ 个字符依次拼接形成的字符串。

给定三个长度均为 $n$ 的仅由小写字母构成的字符串 $a,b,c$，试着找出两个数 $i,j$ 满足 $1<i<j<n$，使得以下表达式最小，并输出这个最小值：

$$\text{LCP}(a_{1\dots i},b_{i+1\dots j})+\text{LCP}(b_{i+1\dots j},c_{j+1\dots n})+\text{LCP}(a_{1\dots i},c_{j+1\dots n})$$

对于 $\operatorname{LCP}(s, t)$ 的定义：设 $s, t$ 是两个字符串，$\operatorname{LCP}(s, t)$ 表示这两个字符串的最长公共前缀。例如若 $s = \texttt{abc}, t=\texttt{abd}$，则 $\operatorname{LCP}(s, t) = 2$。

输入格式

第一行一个整数 $T$，表示测试数据的组数。

接下来，每组测试数据的格式如下。

第一行一个整数 $n$。

接下来三行，每行一个长度为 $n$ 的仅由小写字母构成的字符串，分别表示 $a, b, c$。

输出格式

对于每组测试数据，输出共一行一个整数，表示答案。

1
5
abcbc
abbab
ccbbb

1

样例解释

一种可能的取法是 $i = 3, j = 4$，$\operatorname{LCP}(\texttt{ab}, \texttt{b}) + \operatorname{LCP}(\texttt{b}, \texttt{bb}) + \operatorname{LCP}(\texttt{ab}, \texttt{bb}) = 1$，可以证明不存在更优的选法。

数据规模与约定

对于 $20\%$ 的数据，有 $n\le10$；

对于 $30\%$ 的数据，有 $n\le200$；

对于 $50\%$ 的数据，有 $n\le5000$；

对于上述以外 $20\%$ 的数据，保证给定的字符串中字符为 a 或 b；

对于 $100\%$ 的数据，有 $3\le n \le 10^5, 1\le T\le 3$，字符串中仅会出现小写字母。

下发样例

附件