Hay \(N\) personas sentadas en una mesa circular para una larga sesión de negociaciones. Cada persona pertenece a uno de los tres grupos: \(A, B, C\). Un grupo es feliz si todos sus miembros están sentados de forma contigua en un bloque de asientos consecutivos. Le gustaría hacer felices a todos los grupos mediante alguna secuencia de operaciones de intercambio. En cada operación de permuta, dos personas intercambian asientos entre sí. ¿Cuál es el número mínimo de intercambios necesarios para hacer felices a todos los grupos?

Entrada

La entrada consta de una sola línea que contiene \(N (1≤N≤1000000)\) caracteres, donde cada carácter es A, B o C. La mesa es circular, así que el último está sentado al lado del primero.

Salida

El mínimo número de operaciones de intercambio que pueden realizarse.

Ejemplo de Entrada 1

BABCBCACCA

Ejemplo de Salida 1

2

Explicacion del Ejemplo 1

El primer intercambio daría AABCBCBCCA. El segundo, AABBBCCCCA.