回文着色

题目描述

小红给了小苹一个长度为 $n$ 的 01 串，一开始所有的字符均为黑色，小红希望小苹将所有的字符均涂成红色。为此小苹可以做以下操作任意次：

• 选择一个非空的子序列（可以不连续），满足子序列中所有的字符均为黑色，且此子序列是一个回文的字符串，将这个子序列的所有字符均涂红。

你的任务是帮助小苹求出达成小红的要求所需的最少操作次数。

子序列：子序列为从原字符串中删除（可以不连续）任意个（可以为零）元素得到的新字符串。

输入描述

• 每个测试文件均包含多组测试数据。

• 第一行输入一个整数 $T$（$1 \leq T \leq 10^5$）代表数据组数，每组测试数据描述如下： 一行一个字符串 $s$（$1 \leq |s| \leq 10^6$）。（其中 $|s|$ 表示字符串 $s$ 的长度。）

• 保证输入的 $|s|$ 串仅由 '0' 和 '1' 两种字符构成。

• 除此之外，保证单个测试文件的 $|s|$ 之和不超过 $10^6$。

输出描述

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

示例 1

输入

2
01110001
11111

输出

2
1

说明

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