Palindrome Coloring

题号：NC301282
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红给了小苯一个长度为 $n$ 的 $01$ 串，一开始所有的字符均为黑色，小红希望小苯将所有的字符均涂成红色。
$\hspace{15pt}$ 为此小苯可以做以下操作任意次：
$\hspace{23pt}\bullet\$ 选择一个非空的子序列（可以不连续），满足子序列中所有的字符均为黑色，且此子序列是一个回文的字符串，将这个子序列的所有字符均涂红。

$\hspace{15pt}$ 你的任务是帮助小苯求出达成小红的要求所需的最少操作次数。

$\hspace{15pt}$ 【子序列】子序列为从原字符串中删除（可以不连续）任意个（可以为零）元素得到的新字符串。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

一行一个字符串 。（其中  表示字符串  的长度。）
保证输入的  串仅由  和  两种字符构成。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：
在一行输出一个整数，表示将整个串全部染红的最少操作次数。

示例1

输入

复制

2
01110001
11111

输出

复制

2
1

说明

对于第一组测试数据，一种最优的涂色方案是（红色表示被目前涂红的字符）：
。