Descripción

Maullín, el gato sin identidad, recuerda una etapa de su vida en la que fue jugador \(A\) en un misterioso deporte secreto.

Aunque Maullín ya no recuerda quién era su oponente (solo que era un rival fuerte, guapo y muy sabio), sí conserva la secuencia exacta de quién ganó cada jugada de aquel partido. Ahora, mientras está atrapado tras una puerta con un candado numérico, repasa mentalmente cada una de esas victorias y derrotas, intentando descubrir si él fue, al final, el vencedor.

Reglas del juego

• Cada partido se divide en varios sets.
• Cada set consta de múltiples jugadas.
• En cada jugada, exactamente uno de los dos jugadores gana (\(A\) o \(B\)).
• Un jugador gana un set cuando alcanza exactamente X victorias en ese set; en ese momento el set finaliza y comienza el siguiente.
• El partido completo termina cuando uno de los jugadores gana Y sets; ese jugador se declara ganador del partido.
• Los valores de X y Y son secretos y Maullín no los recuerda.

Maullín solo recuerda la secuencia de resultados de las jugadas, por ejemplo esta es una secuencia de una partida:

Maullín solo recuerda la secuencia de resultados de las jugadas, por ejemplo esta es una secuencia: \(ABBAA\), en este caso, el juego pudo haberse jugado con X = 3, Y = 1. Para la cadena \(ABBAA\) el jugador \(A\) gana las tres primeras jugadas del set y, con Y = 1, es declarado ganador del partido.
También podría ganar con X = 1, Y = 3, pero no existen valores de X y Y para los cuales \(B\) termine siendo ganador.

Otro ejemplo de una cadena es \(AAAA\), en este caso el jugador \(A\) gana todas las jugadas, por lo que cualquier valor válido para X y Y el jugador \(A\) acumula los sets necesarios primero y es el ganador seguro.

Entrada

• Una línea con un entero \(n\), el número de casos.
• Para cada caso, una cadena \(s\) formada solo por caracteres \(A\) y \(B\):
  • A indica que Maullín ganó esa jugada.
  • B indica que su oponente ganó esa jugada.
  • Se garantiza que la secuencia \(s\) corresponde a al menos un escenario válido de valores X y Y.

Salida

Para cada uno de los \(n\) casos, imprime un solo carácter:

• A si Maullín (jugador \(A\)) ganó el partido completo.
• B si su oponente (jugador \(B\)) ganó el partido completo.

Ejemplos

Entrada

1
AAAAAAAABBBAABBBBBAB

Salida

B

Explicación El juego pudo haberse jugado con los valores X = 3, Y = 3:

• En el primer set se jugaron 3 jugadas: AAA. El jugador \(A\) gana el set.
• En el segundo set se jugaron 3 jugadas: AAA. El jugador \(A\) gana el set.
• En el tercer set se jugaron 5 jugadas: AABBB. El jugador \(B\) gana el set.
• En el cuarto set se jugaron 5 jugadas: AABBB. El jugador \(B\) gana el set.
• En el quinto set se jugaron 4 jugadas: BBAB. El jugador \(B\) gana el set.

En total, el jugador \(B\) fue el primero en ganar 3 sets y se declara ganador del juego.

Entrada

2
ABBAA
AAAA

Salida

A
A

Entrada

2
BAABB
BBBB

Salida

B
B

Entrada

2
AAABA
BABB

Salida

A
B

Límites

• \(1 \leq n \leq 10^5\)
• \(1 \leq s_i \leq 20\)