题目描述

给定一个字符串 $s$，你可以对字符串 $s$ 执行三种编辑操作：

• 插入一个字符
• 删除一个字符
• 将某个字符替换为另一个字符

问最少几次操作使得字符串 $s$ 是回文的。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示 $t$ 组数据。对于每一组数据：

• 输入一个字符串 $s$，仅由小写字母构成。

输出格式

对于每个测试用例，输出一个整数表示答案。

6
aaaaba
hello
palindrome
abba
x
bababac

1
2
5
0
0
1

提示

数据范围

• $1 \le t \le 200$
• 字符串 $s$ 长度至少为 1。
• 保证所有测试用例中字符串 $s$ 长度之和不超过 $3000$。