Tarkastellaan kahden pelaajan peliä, jossa on n vierekkäistä mukia. Tarkalleen kahdessa mukissa on aluksi pallo.

Joka vuorolla pelaaja valitsee toisen pallon ja siirtää sen vasemmalla tai oikealla olevaan tyhjään mukiin. Kuitenkaan pelaaja ei saa kumota välittömästi toisen pelaajan tekemää edellistä siirtoa.

Pelaaja 1 aloittaa ja pelin häviää se, joka ei pysty tekemään siirtoa. Kumpi pelaaja voittaa, jos molemmat pelaavat optimaalisesti?

Syöte

Ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen on t riviä, joista jokainen kuvaa yhden testin. Rivillä on pelin aloitustilanteen kuvaus merkkijonona, jossa . tarkoittaa tyhjää kuppia ja P tarkoittaa kuppia, jossa on pallo.

Tuloste

Tulosta jokaisesta testistä voittavan pelaajan numero.

Esimerkki

Syöte:

5
PP
P.P
...P...P
.P....P.
..PP

Tuloste:

2
1
1
2
2

Osatehtävä 1 (35 pistettä)

• 1 \le t \le 100
• 1 \le n \le 10

Osatehtävä 2 (65 pistettä)

• 1 \le t \le 100
• 1 \le n \le 100