字符串合成

内存限制：256 MiB 时间限制：5 Sec

提交提交记录讨论

给定四种对字符串 S 的操作：

(1) push_back( P )：在 S 后连接一个字符串 P，即 S = S + P，代价为| P |；

(2) push_front( P )：在 S 前连接一个字符串 P，即 S = P + S，代价为| P |；

(3) symmetry_back( )：将 S 翻转后连接在 S 之后，即 S = S + rev(S)，代价为 1；

(4) symmetry_front( )：将 S 翻转后连接在 S 之前，即 S = rev(S) + S，代价为 1；

给定一个目标串 S，要求你通过上述四种操作，用最少的代价合成出目标串。初始只有一个空串。

第一行一个正整数 T，表示数据组数。接下来 T 行，每组数据一行，为字符串 S。

1 <= |S| <= 100000， T <= 10

每组数据一行输出一个正整数,Cost表示最少的代价

样例输入


			7 

c

aaaab

bbaaaacc

ababa

abba

baab

aaabacdbbdcabaaaaaaaaaaaab

样例输出


			1 

4 

7 

5 

3 

3

18

//{} -> c，代价为 1

{} -> aa -> aaaa -> aaaab，代价为 2 + 1 + 1 = 4

{} -> aa -> aaaa -> aaaacc -> bbaaaac，代价为 2 + 1 + 2 + 2 = 7

{} -> ababa，代价为 5

{} -> ab -> abba，代价为 2 + 1 = 3

{} -> ab -> baab，代价为 2 + 1 = 3

{} -> aaa -> aaaaaa -> baaaaaa -> baaaaaaaaaaaab -> aaabacdbbdcabaaaaaaaaaaaab，

代价为 3 + 1 + 1 + 1 + 12 = 18

#4163. 字符串合成

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示