回文串修改

所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的 比如 "aba” 。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字 符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几 个字符，可以使这个字符串成为回文字符串。

输入格式

输入第一行给出整数 $N(0<N≤100)$ 下来的N行，每行一个字符串，每个字符 串长度不超过 $1000$。

输出格式

每行输出所需添加的最少字符数。

1
Ab3bd

2

提示

数据范围与提示

$0<N≤100$

时间限制: 1000ms

内存限制: 128MB