题目描述

Skibidus 得到了一个由小写拉丁字母组成的字符串 $s$。如果 $s$ 的长度大于 $1$，他可以执行以下操作：

选择一个下标 $i$（$1 \le i \le |s|-1$，$|s|$ 表示字符串 $s$ 的当前长度），存在 $s_i = s_{i+1}$。 将 $s_i$ 替换为他所选择的任意小写拉丁字母，并从字符串中删除 $s_{i+1}$。

Skibidus 想知道，通过执行任意次数的上述操作，他能将字符串缩短到的最小可能长度是多少。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100$) — 测试用例的数量。

每个测试用例包含唯一的一行，为一个字符串 $s$ ($1 \le |s| \le 100$)。保证 $s$ 仅由小写拉丁字母组成。

输出格式

对于每个测试用例，在新的一行输出一个整数，表示字符串 $s$ 可达到的最小可能长度。

样例

输入样例

4
baa
skibidus
cc
ohio

输出样例

1
8
1
4

说明/提示

在第一个测试用例中（字符串为 baa），Skibidus 可以：

• 对 $i=2$ 执行操作。他将 $s_2$ 替换为 b，并从字符串中删除 $s_3$。此时，字符串 $s$ 变成了 bb。
• 对 $i=1$ 执行操作。他将 $s_1$ 替换为 b，并从字符串中删除 $s_2$。此时，字符串 $s$ 变成了 b。 因为此时 $s$ 的长度仅为 $1$，Skibidus 无法再执行任何操作。因此，第一个测试用例的答案是 $1$。

在第二个测试用例中（字符串为 skibidus），他无法在任何下标处执行操作（因为没有任何两个相邻字母相同）。

因此，答案仍然是初始字符串的长度，即 $8$。

限制

每次测试时间限制: 1 秒
每个测试的内存限制: 256 MB
输入: 标准输入
输出: 标准输出