#P18547. Bot Friends
Bot Friends
Bot Friends
小青鱼有 位机器人朋友,位于一条数轴上。第 个机器人的位置是 ()。数轴上还有 个洞,第 个洞的位置是 ()。
开始时,所有机器人都没有被激活。小青鱼可以按任意顺序,逐个激活这些机器人。机器人被激活时,会选择向左或向右移动,其类型对方向有如下限制:
<型只能向左移动。>型只能向右移动。?型可以选择向左或向右移动。
机器人会一直沿选定方向移动,直到掉进一个尚未被占据的洞。此时它停止移动,并占据这个洞。如果机器人到达坐标 或 ,它就会消失。
如果起初位于 的机器人掉进了位置为 或 的洞,则称它是坏机器人;否则称它是好机器人。
小青鱼希望选择每个 ? 型机器人的移动方向,并安排激活顺序,使好机器人的数量尽可能多。求最多可以有多少个好机器人。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例包含一行字符串,长度为 ()。每个字符都是 <、> 或 ?,按顺序表示机器人的类型。输入中不另外给出 。
保证一个输入文件中所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一行一个整数,表示最多能得到的好机器人数量。只需输出数量。
样例
10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
2
2
3
4
5
8
7
8
5
6