题目背景

在测试完笔记本后，CodingCow 又有了一些新想法。CodingCow 找来了一些笔记本相关产品的设计师，统计下了他们的名字。但是由于 CodingCow 的笔记本空间严重不足了。需要压缩以下这些名字，需要你帮帮忙！

题目描述

给定 $n$ 个字符串，对于任意一个字符串 $s$ ，我们可以删除相邻的两个不同的字符，求每个字符串可以通过操作获得的最短的字符串长度。

输入格式

输出第一行一个数 $n$ 。

此后 $n$ 行，每行一个字符串 $s_i$ 。

输出格式

输出共 $n$ 行，每行一个数，表示该字符串可以被缩减到的字符串的长度的最小值。

样例

7
ssdodbsna
bumqmoac
rfqcm
mxdj
e
wycut
zmtrktxafv

1
0
1
0
1
1
0

10
jecmozuf
y
xa
qaymoll
mdiqakir
ovucqc
d
nisw
na
xpbicqeo

0
1
0
1
0
0
1
0
0
0

见 "sample_problem2.zip/sample/2.in"

见 "sample_problem2.zip/sample/2.ans"

提示

本题读入量巨大，请务必使用较快的输入方式。

寄语

“为了岩王帝君，风雪的缩影，如琉璃般飘落，这项工作该划掉了。”

附件

sample_problem2.zip。

数据范围

对于 $40 \%$ 的数据，$1 \le n \le 100$，$1 \le |s_i| \le 100$。

对于 $100 \%$ 的数据，$1 \leq n\leq 10^5$，$1 \le |s_i| \le 1000$，$\forall ch \in s_i,\,ch \in [a, z]$ （字符串 $s_i$ 由小写字母组成）。