字符串 $s$ 的一个划分是指一组一个或多个非重叠、非空的 $s$ 的子串（记为 $a_1, a_2, a_3, \dots, a_d$），使得它们连接起来等于 $s$：$s = a_1 + a_2 + a_3 + \dots + a_d$。我们将这些子串称为“块”，并将该划分的长度定义为块的数量 $d$。

我们可以通过将每个块括在括号中来表示字符串的划分。例如，字符串 "decode" 可以划分为 (d)(ec)(ode) 或 (d)(e)(c)(od)(e) 或 (decod)(e) 或 (decode) 或 (de)(code) 等多种方式。

如果一个划分中的块在将每个块视为一个原子单位时构成一个回文序列，则称该划分为回文划分。例如，"decode" 仅有的回文划分为 (de)(co)(de) 和 (decode)。这也说明了每个单词都有一个长度为 1 的平凡回文划分。

你的任务是计算回文划分中块的最大可能数量。

输入格式

输入的第一行包含测试用例的数量 $t$。接下来的 $t$ 行描述了各个测试用例，每行包含一个单词 $s$，仅由小写英文字母组成。输入中没有空格。

输出格式

对于每个测试用例，输出一个数字：输入单词 $s$ 的最长回文划分的长度。

数据范围

设输入字符串 $s$ 的长度为 $n$。

• $1 \le t \le 10$
• $1 \le n \le 10^6$

子任务 1（15 分）

• $n \le 30$

子任务 2（20 分）

• $n \le 300$

子任务 3（25 分）

• $n \le 10\,000$

子任务 4（40 分）

• 无附加限制

样例

输入 1

4
bonobo
deleted
racecar
racecars

输出 1

3
5
7
1