题目描述

定义“平方字符串”，意思为一个字符串s[1…n]，其中子串s1[1…k]和s2[k+1…n]完全相等。例如”abab”,”aaaa”是平方字符串，”aba”,”abca”就不是。

有如下几种操作：

1.将任意一个字符替换成另外一个字符 2.可以在字符串的任意一个地方插入一个字符 3.可以删去字符串的任意一个字符

给一个初始字符串，问经过上述操作最少几次能够将该字符串变成“平方字符串”。

输入输出格式

输入

第一行输入一个数T，表示测试数据个数，对于每个测试数据输入一个字符串，表示初始的字符串，字符串长度<=100。

输出

对于每个测试数据输出一个数，表示最少操作次数。

样例

输入1

3
abcdabcmd
abcdabyd
abcdabcd

输出1

1
1
0

时间及空间限制

1s, 256MB.