Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AI_GS - Gente Subnormal

Uno de los problemas en toda Bolivia es que los habitantes son muy irresponsables a la hora de cruzar las calles. Simplemente ven que “no hay autos” o “los autos están lejos” para correr hacia el otro lado, lo cual produce accidentes de vez en cuando.

Un día el gobierno se hartó de la situación y decidió cercar las aceras (brillante idea), de modo que los ciudadanos comenzaron a quejarse de que muchos de los caminos se cerraron y no se puede llegar a algunos lugares. De todas formas no mejoró mucho la situación: la gente es irresponsable y sigue pasando a través del tráfico cuando puede. Al final decidieron colocar pasarelas para que se pueda cruzar de manera segura; sin embargo, una persona que está intentando cruzar una calle transitada solo preferirá utilizar una pasarela si esta se encuentra ubicada en el tramo en que ella está o en alguno de los adyacentes.

El gobierno está buscando minimizar el gasto que va a tener (porque ya gasto mucho de su presupuesto en construir las cercas) y pide tu ayuda para saber cuál es la cantidad mínima de pasarelas que debe construir en una calle de tal manera que cualquier persona que esté considerando cruzar por un tramo vacío (sin ninguna cerca o pasarela) prefiera siempre utilizar una pasarela cercana.

Para propósitos analíticos, se puede representar una calle como una cadena de caracteres. Cada uno de los caracteres representa un tramo de la calle y puede ser: '. ', 'C' o 'P'.

  • La letra 'C' indica que este tramo tiene colocada una cerca (la gente no intentará cruzar por ahí). De todas formas, el gobierno podría construir una pasarela aquí.
  • La letra ‘P’ indica que ya existe una pasarela en este tramo.
  • El símbolo ‘.’ (punto) indica que este tramo está vacío (la gente podría intentar cruzar). El gobierno podría construir una pasarela aquí.

Entrada

La entrada comienza con un número T en una sola línea que indica la cantidad de calles que debes analizar (1 <= T <= 200). A continuación siguen T líneas. Cada línea consta de hasta 10.000 caracteres que describen una calle en la cual el gobierno está interesado en construir.

Salida

Por cada calle, imprima una línea con un número que indique la respuesta al problema.

Ejemplo de Entrada:
3
...
...C.
CPC.C.

Ejemplo de Salida:
1
2
1


Adicionado por:Hernan Payrumani
Fecha:2014-09-27
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP CPP C++ 4.3.2 CPP14 JAVA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.