题目描述

点此下载 2024 年实验室二面题解

在我的世界中，沙块只能被放在其它方块之上(不能悬浮，沙块也属于方块)，当其下方块消失时，沙块会一直掉落直至其下方有方块为止。现在有一个高度为$n$的沙块堆，其中的沙块有4种不同颜色：白-绿-黑-红(分别用$a,b,c,d$表示), 其之间有克制关系($a$被$b$克，$c$被$d$克)，当有克制关系的沙块相邻且被克制的沙块在下方时，这两个沙块会迅速消失。

给你一串长度为$n$且仅由$a,b,c,d$组成的字符串表示地面上自下往上堆成的高度为n的沙块堆，请你回答这个沙堆的最终高度是多少。

输入描述

第一行输入一个$T$表示$T$组数据。

接下来$T$行每行输入一个字符串代表沙块堆。

$1<=T<=100, 1<=n<=1e5$

输出描述

输出T行，每行一个整数表示沙堆最终高度。

示例 1

输入

1
abaacdb

输出

1

说明

第一个测试用例中，容易观察到：第1个沙块被第2个沙块克制，所以会消失，接着第5个沙块被第6个沙块克制，会直接消失，然后第7个沙块掉落到第4个沙块上，第4个沙块会被第7个沙块克制，然后消失，最后仅剩下第3个沙块(这里所描述的下标都是相对原字符串)。