Little Cyan Fish 有 $n$ 个机器人朋友（简称 bots），它们位于数轴上。第 $i$ 个机器人位于位置 $i + 0.5$，其中 $1 \le i \le n$。此外，数轴上还有 $n + 1$ 个洞，第 $i$ 个洞位于位置 $i$，其中 $1 \le i \le n + 1$。

最初，所有机器人都是未激活的。Little Cyan Fish 按任意顺序依次激活这些机器人。激活后，机器人根据其类型向左或向右移动，规则如下：

• 类型为 “<” 的机器人只能向左移动。
• 类型为 “>” 的机器人只能向右移动。
• 类型为 “?” 的机器人可以选择向左或向右移动。

机器人会沿着选择的方向持续移动，直到掉进一个未被占用的洞，此时它会停下并占据该洞。如果机器人到达位置 $0$ 或位置 $n + 2$，它就会消失。

目标是避免出现“坏”机器人，定义如下：如果位于位置 $i + 0.5$ 的机器人掉进了位置 $i$ 或 $i + 1$ 的洞中，则该机器人被视为“坏”的。否则，它被视为“好”的。

Little Cyan Fish 面临的挑战是确定每个 “?” 类型机器人的移动方向以及激活顺序，使得“好”机器人的数量最大化。请帮助 Little Cyan Fish 找到一种最优的方案来分配方向并激活机器人，并求出“好”机器人的最大数量。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个长度为 $n$ ($1 \le n \le 5000$) 的字符串。字符串中的每个字符为 “<”、“>” 或 “?”，表示第 $i$ 个机器人的类型。

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

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

样例输入 1

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

样例输出 1

2
2
3
4
5
8
7
8
5
6