P14015 [ICPC 2024 Nanjing R] 生日礼物

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 能得到的最短序列的长度。