题目描述

翁老师得到一个由小写字母构成的字符串 $s$，若 $s$ 的长度大于 $1$，则可以：

• 选择一个位置 $i$，其中 $1\leq i\leq |s|-1$（$|s|$ 指 $s$ 的长度），若满足 $s_i=s_{i+1}$，则可以在字符串 $s$ 中删除 $s_{i+1}$，同时将 $s_i$ 替换为任意一个字符。

显然每执行一次操作可以使得字符串长度减 $1$，请问字符串长度最少可以变为多少？

输入格式

本题有多组测试数据

第一行输入一个整数 $t$ 代表测试数据组数。

接下来 $t$ 行，每行输入一个字符串 $s$。

输出格式

输出一共输出 $t$ 行，每一行一个整数代表答案。

4
baa
skibidus
cc
ohio

1
8
1
4

提示

样例 1 解释

第一组数据，可以先将 baa 修改为 bb，然后在修改为 b，使得长度变为 $1$。

数据范围

对于 $100\%$ 的数据，$(1\leq t\leq 100,1 \leq |s| \leq 100)$

• 子任务 $1$（$30$ 分）：字符串的所有字母均 相同。
• 子任务 $2$（$30$ 分）：字符串的所有字母均 不相同。
• 子任务 $3$（$40$ 分）：没有特殊限制。