El joc de les dames consta de 24 peons (fitxes), dividits en 12 blancs i 12 negres, i un tauler de 64 caselles (8×8) acolorides alternativament blanques i negres. La finalitat del joc és la captura o bloqueig de totes les peces contràries, de manera que no els sigui possible fer moviment. Cada jugador controla les peces d'un color situades al començament a cada costat del tauler. Comença el joc les blanques.

Els moviments es fan alternativament, un per jugador, en diagonal, una sola casella i en sentit d'avanç, és a dir, cap al camp de l'oponent. Si un jugador aconsegueix portar una de les fitxes al costat contrari del tauler canviarà aquest peó per una dama o reina (dues fitxes del mateix color una damunt l'altra). Aquesta peça disposa de habilitats especials que ara no tractarem.

Una peça en pot capturar una altra si en pot saltar per sobre sempre en direcció d'atac i en diagonal i caure a la casella immediatament darrere d'aquella.

La captura és obligatòria. Si una o més peces estan en situació de fer captures, serà obligatori fer aquesta captura, no podent optar per moure una altra peça. Un cop realitzada una captura, han de tornar a capturar si és possible segons les regles anteriors i al mateix torn del jugador, i així successivament.

Entrada

L’entrada conté una primera línia amb el número de casos de prova a tractar. A continuació, per cada cas de prova s’introdueix 8 línies amb la situació del tauler del joc en un moment donat. La simbologia que farem servir per representar el tauler és:

• Peó negre - PN
• Peó blanc - PB
• Casella buida - bb Les peces blanques es situen inicialment en les files 0, 1 i 2 del taulell, i les peces negres a les files, 5, 6 i 7; repartides ambdues per les caselles pintades de negre.

Finalment, es llegirà una línia amb dos números que indiquen la posició del tauler (fila, columna) on es troba la fitxa que es vol moure en aquest moment. La casella que es troba a la cantonada superior esquerra, correspon a la (0,0) i la casella de la cantonada inferior dreta és la (7,7)

Sortida

Per cada cas de prova mostrar el nombre màxim de peces que es pot menjar del contrari la peça seleccionada.

Exemple d'Entrada

3
bb PB bb PB bb PB bb PB
PB bb PB bb PB bb PB bb
bb PB bb PB bb PB bb PB
bb bb bb bb bb bb bb bb
bb bb bb bb bb bb bb bb
PN bb PN bb PN bb PN bb
bb PN bb PN bb PN bb PN
PN bb PN bb PN bb PN bb
2 3
bb PB bb PB bb PB bb PB
PB bb PB bb PB bb PB bb
bb bb bb PB bb PB bb PB
bb bb PB bb PN bb bb bb
bb bb bb PN bb bb bb bb
PN bb PN bb bb bb PN bb
bb PN bb PN bb PN bb PN
PN bb bb bb PN bb PN bb
3 2
bb PB bb PB bb PB bb PB
PB bb PB bb PB bb PB bb
bb bb bb PB bb PB bb PB
bb bb PB bb PN bb bb bb
bb PN bb PN bb bb bb bb
bb bb PN bb bb bb PN bb
bb PN bb PN bb PN bb PN
PN bb PN bb PN bb bb bb
3 2

Exemple de Sortida

0
2
2