Descripción

Suzie Kepere está en medio de un juego. En este juego, ella debe usar bombas para bombardear una cadena compuesta por las letras "A" y "B". Puede usar bombas para bombardear una subcadena que sea "AB" o "BB". Al bombardear una subcadena de este tipo, esta se elimina de la cadena y las partes restantes se concatenan.

Por ejemplo, Suzie puede usar dos operaciones como: AABABBA \(→\) AABBA \(→\) AAA.

Suzie Kepere se pregunta cuál es la cadena más corta que puede formar. ¿Puedes ayudarle a encontrar la longitud de la cadena más corta?

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene un entero \(t\) \((1≤t≤20000)\) \(-\) el número de casos de prueba. A continuación, se describe cada caso de prueba.

Cada una de las siguientes \(t\) líneas contiene un caso de prueba, que consiste en una cadena no vacía \(s\) \(-\) la cadena que Suzie necesita bombardear. Se garantiza que todos los símbolos de \(s\) sean 'A' o 'B'.

Se garantiza que la suma de \(|s|\) (longitud de \(s\)) entre todos los casos de prueba no exceda \(2⋅10^5\).

Salida

Para cada caso de prueba, imprime un solo entero: la longitud de la cadena más corta que Suzie puede crear.

Ejemplo

Entrada

3
AAA
BABA
AABBBABBBB

Salida

3
2
0

Nota

Para el primer caso de prueba, no se pueden realizar movimientos, por lo que la respuesta es \(3\). Para el segundo caso de prueba, una secuencia óptima de movimientos es BABA \(→\) BA. Por lo tanto, la respuesta es \(2\). Para el tercer caso de prueba, una secuencia óptima de movimientos es AABBBABBBB \(→\) AABBBABB \(→\) AABBBB \(→\) ABBB \(→\) AB \(→\) (cadena vacía). Por lo tanto, la respuesta es \(0\).