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; an employee always uses an empty chair first, and a chair is bought only when there is no empty one. 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. This site's addition: every simulation is a valid event sequence; when R/L is executed at least one employee is in the room, and when U is executed at least one employee is in the meeting room. Employee identities are not distinguished; only the headcount states above must be respected.

输入格式

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

输出格式

Output n space-separated integers in input order, each being the minimum number of chairs that must be bought for that simulation.

样例 1

输入：

1
C

输出：

1

样例 2

输入：

1
CCCRLCC

输出：

3

样例 3

输入：

1
CCRRCRUU

输出：

2