在弗兰肯瑞士（Franconian Switzerland），有一条狭窄的山路。由于只有单车道，这里成为了双向交通的瓶颈。你的任务是调度两端的驶入车辆，使得最后一辆车离开山路的时间尽可能早。

每辆车由三个值确定：行驶方向、到达对应山路起点的时间，以及在不受前方车辆阻碍的情况下通过山路所需的行驶时间。车辆在山路上不能超车，且不允许在山路两端的队列中重新排序。

出于安全原因，两辆连续向相同方向行驶的车辆通过山路上任意点的时间间隔不得少于 $10$ 秒。这确保了如果前车紧急刹车，后车不会撞上它。然而，如果在此期间有另一辆车向相反方向通过，则表明道路已空，因此在这种情况下，该规则不适用。

输入格式

输入的第一行包含一个整数 $c$ ($1 \le c \le 200$)，表示测试用例的数量。

接下来是各个测试用例，每个测试用例开头包含一行，有一个整数 $n$ ($1 \le n \le 200$)，表示在该测试用例中需要考虑的车辆数量。

每个测试用例的其余部分由 $n$ 行组成，每行代表一辆车，以一个大写字母（“A”或“B”）开头，表示车辆的行驶方向。接下来在同一行中，有两个整数 $t$ ($0 \le t \le 100\,000$) 和 $d$ ($1 \le d \le 100\,000$)，分别表示车辆到达山路起点的时间和最小行驶时间，单位均为秒。

在一个测试用例中，车辆按到达时间递增的顺序给出，且没有两辆车会同时到达。

输出格式

对于每个测试用例，输出一行，包含在最优调度下最后一辆车离开山路的时间点（以秒为单位）。

样例

输入样例 1

2
4
A 0 60
B 19 10
B 80 20
A 85 100
4
A 0 100
B 50 100
A 100 1
A 170 100

输出样例 1

200
270