Chairs Requirement

Given several simulations of employees coming and going, find the minimum number of chairs that must be bought for each simulation. Initially there are no chairs; employees always use an empty chair first, and one chair is bought whenever no empty chair is available. C means a new employee enters, R means an employee temporarily goes to the meeting room, U means an employee returns from the meeting room, and L means an employee leaves permanently. Added by this site: every simulation is a valid event sequence; when R/L is performed, at least one employee is in the office, and when U is performed, at least one employee is in the meeting room. Employees are not distinguished; only the headcount states above need to be respected.

The problem meaning, function, and constraints are the same as in the original Goldman Sachs #24 statement. The guarantee that every simulation sequence is valid is an input guarantee added by this site to make the output unique, not a condition stated in the original.

输入格式

The first line contains n; each of the next n lines contains one simulation string consisting only of C, R, U, L. 1≤n≤100, 1≤length of each string≤10000.

输出格式

Output n integers in input order, separated by spaces; each is the minimum number of chairs to buy for that simulation.

样例 1

输入：

1
C

输出：

1

样例 2

输入：

1
CCCRLCC

输出：

3

样例 3

输入：

1
CCRRCRUU

输出：

2