题目描述

Grammy 的生日快要来了，她从她的朋友那里获得了一个序列 $A$ 作为礼物。序列由 $0$，$1$ 和 $2$ 构成。Grammy 觉得这个序列太长了，所以她打算把 $A$ 修改得短一些。

更正式地，Grammy 可以执行任意次操作。每次她可以执行以下三种操作之一：

• 将任意一个 $2$ 改为 $0$ 或 $1$。
• 选择两个相邻的 $0$，删除它们，并将剩下的部分连接起来。
• 选择两个相邻的 $1$，删除它们，并将剩下的部分连接起来。

求 Grammy 能得到的最短序列的长度。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个长度为 $n$ 的字符串（$1\leq n\leq 2 \times 10^5$）。字符串由数字 $0$，$1$ 和 $2$ 构成，表示初始序列 $A$。

保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

输出格式

每组数据输出一行一个整数，表示 Grammy 能得到的最短序列的长度。

5
0110101
01020102
0000021111
1012121010
0100202010

3
4
0
6
0