徐老师的回文01
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
《为了简化题意，这道题目的题目描述将会很短》徐老师有一个 $01$ 串，现在可以在任意位置插入 $1$
请问最少插入几个 $1$ 可以使得这个字符串变成回文串？
P.S. 回文串是指从左往右看和从右往左看是一样的字符串
输入格式
本题采用多组测试数据输入第一行包含一个正整数 $T$，表示一共有 $T$ 组数据。
对于每组测试数据，输入一行包含一个字符串，保证该字符串只由 $0/1$ 组成
| 测试点编号 | 字符串长度 |
| :---: | :---: |
| $1 \sim 3$ | $\leq 10$ |
| $4 \sim 8$ | $\leq 1000$|
| $9 \sim 10$ | $\leq 100000$|
对于所有测试数据有：$1 \leq T \leq 20$
| :---: | :---: |
| $1 \sim 3$ | $\leq 10$ |
| $4 \sim 8$ | $\leq 1000$|
| $9 \sim 10$ | $\leq 100000$|
对于所有测试数据有：$1 \leq T \leq 20$
输出格式
对于每组测试数据输出最少需要插入几个 $1$ 才能使字符串变成回文串样例
4
10101
00001
01001101
11100
1
2
3
