两个字符串 $u$ 和 $v$ 之间的编辑距离是将 $u$ 转换为 $v$ 所需的最少编辑操作次数。可以对字符串进行三种编辑操作：插入一个字符、删除一个字符，以及将某个字符替换为另一个不同的字符。

例如，我们可以通过四次替换将 hello 转换为 world，因此编辑距离至多为 4。你可以通过两次替换和一次插入将 wally 转换为 walter，因此编辑距离至多为 3。计算两个字符串之间的编辑距离是一个众所周知的问题，有着广泛的应用。

当前的任务是计算一个字符串到与其最近的回文串之一的编辑距离。回文串是指正读和反读都相同的字符串，例如 madam。

hello 到最近回文串的编辑距离仅为 2：我们可以通过两次编辑操作将 hello 转换为 ollo、hllh 或 elle。

编写一个程序，寻找一个单词到最近回文串的距离。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$。接下来是测试用例的描述。

每个测试用例的唯一一行包含一个仅由小写字母组成的单词 $w$。

输出格式

对于每个测试用例，输出输入单词 $w$ 到其最近回文串的编辑距离。

数据范围

• $1 \le t \le 200$
• 单词 $w$ 的长度至少为 1。
• 保证所有测试用例中单词 $w$ 的长度之和不超过 3000。

样例

输入样例 1

6
aaaaba
hello
palindrome
abba
x
bababac

输出样例 1

1
2
5
0
0
1