题目描述

奶奶的生日快到了，她从朋友们那里收到了一串序列 $A$ 作为礼物。这个序列仅由数字 $0$、$1$ 和 $2$ 组成。奶奶觉得序列太长了，因此她决定修改 $A$ 以使其更短。

具体来说，奶奶可以进行任意次数的操作。每次她可以选择执行以下三种操作之一：

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

计算奶奶可以得到的最短序列长度。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个长度为 $n$ 的字符串（$1 \leq n \leq 2 \times 10^5$），表示初始序列 $A$。字符串仅包含数字 $0$、$1$ 和 $2$。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行包含一个整数，表示奶奶可以得到的最短序列长度。

样例

5  
0110101  
01020102  
0000021111  
1012121010  
0100202010

3
4
0
6
0