P15896 [TOPC 2025] Palindromic Distance

两个字符串 $u$ 和 $v$ 之间的编辑距离，是指将 $u$ 转换为 $v$ 所需的最少编辑操作次数。可以对字符串应用三种编辑操作：插入一个字符、删除一个字符，以及将某个字符替换为另一个不同的字符。 例如，我们可以通过四次替换将 **hello** 转换为 **world**，因此编辑距离至多为 4。通过两次替换和一次插入可以将 **wally** 转换为 **walter**，因此编辑距离至多为 3。计算两个字符串之间的编辑距离是一个经典问题，具有广泛的应用。 当前的任务是计算一个字符串到 **最近的回文串** 的编辑距离。回文串是指正反读起来相同的字符串，例如 **madam**。 字符串 **hello** 到最近回文串的编辑距离仅为 2：我们可以通过两次编辑操作将 **hello** 转换为 **ollo**、**hllh** 或 **ellle**。 请编写一个程序，找出一个单词到最近回文串的距离。

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$，接下来是每个测试用例的描述。 每个测试用例只有一行，包含一个单词 $w$，仅由小写字母组成。

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

- $1 \le t \le 200$ - 单词 $w$ 的长度至少为 1。 - 保证所有测试用例中单词 $w$ 的长度之和不超过 $3000$。 翻译由 DeepSeek V3.2 完成