You are on a circular path of infinite radius. From your initial position, you can move either in the clockwise direction or in the anticlockwise direction but only along the circular path. Your movements are represented by a string $$S$$ of length $$L$$. This string can consist of three different types of characters, each denoting a move:

• A: You move 1 unit in the anticlockwise direction
• C: You move 1 unit in the clockwise direction
• ?: You move 1 unit either in the clockwise or the anticlockwise direction

Write a program to find the maximum distance from your initial position in any direction at any point of time.

Input format

• First line: $$T$$ (number of test cases)
• Next $$T$$ lines: $$S$$

Output format

For each test case, print the maximum distance from the initial position in any direction at any point of time.

Constraints

\(1 \le T \le 10\)
\(1 \le Length \; of \; string \le 10^5\)