#P18547. Bot Friends

Bot Friends

Bot Friends

小青鱼有 nn 位机器人朋友,位于一条数轴上。第 ii 个机器人的位置是 i+0.5i+0.5(1≤i≤n1\le i\le n)。数轴上还有 n+1n+1 个洞,第 ii 个洞的位置是 ii(1≤i≤n+11\le i\le n+1)。

开始时,所有机器人都没有被激活。小青鱼可以按任意顺序,逐个激活这些机器人。机器人被激活时,会选择向左或向右移动,其类型对方向有如下限制:

  • < 型只能向左移动。
  • > 型只能向右移动。
  • ? 型可以选择向左或向右移动。

机器人会一直沿选定方向移动,直到掉进一个尚未被占据的洞。此时它停止移动,并占据这个洞。如果机器人到达坐标 00 或 n+2n+2,它就会消失。

如果起初位于 i+0.5i+0.5 的机器人掉进了位置为 ii 或 i+1i+1 的洞,则称它是坏机器人;否则称它是好机器人。

小青鱼希望选择每个 ? 型机器人的移动方向,并安排激活顺序,使好机器人的数量尽可能多。求最多可以有多少个好机器人。

输入格式

第一行一个整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

每个测试用例包含一行字符串,长度为 nn(1≤n≤50001\le n\le5000)。每个字符都是 <、> 或 ?,按顺序表示机器人的类型。输入中不另外给出 nn。

保证一个输入文件中所有测试用例的 n2n^2 之和不超过 5×1075\times10^7。

输出格式

对于每个测试用例,输出一行一个整数,表示最多能得到的好机器人数量。只需输出数量。

样例

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
2
2
3
4
5
8
7
8
5
6