Problem Statement

You are given a string $S$ consisting of A, B, and C.

You can perform the following operation zero or more times.

• Choose a substring (contiguous subsequence) of $S$ that is A, AB, or ABC, and delete it. The remaining characters are concatenated, preserving their order.

Find the minimum possible length of $S$ in the end.

$T$ test cases are given; solve each of them.

Constraints

• $T$ is an integer between $1$ and $10^5$, inclusive.
• $S$ is a string consisting of A, B, and C with length between $1$ and $10^6$, inclusive.
• The sum of $|S|$ in each input is at most $10^6$.

Input

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

S

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.