SP17394 DCEPC12B - Bits Game

Pranjali and Nancy are playing an amazing game. The game starts with a string of bits (i.e. string of 0’s and 1’s). Game progresses in the form of right to left bit by bit scans. Pranjali takes turn when a “1” bit comes while scanning the string and Nancy takes turn when a “0” bit comes while scanning. In their respective turns, they can either choose to toggle their bit or keep it unchanged. The goal is to make all bits 0 at the end of scan, failing which means the scanning starts again from right to left. If all the bits are 0 at the end of a scan, the game ends and Pranjali is declared a winner. There is no win for Nancy. The game either ends to the goal described or the scanning continues indefinitely. So it can be seen that Pranjali has to win the game and in an optimal number of scans whereas Nancy’s aim is to not let Pranjali win (by making it an indefinite play) or to delay Pranjali’s win if it’s sure. So now assuming that they both play with their optimal strategy, can you please tell if Pranjali can win the game or not? Note: There has to be AT LEAST 1 scan before the game can end.

First line contains T, the number of test cases. Each of the next T lines contains a string of 0’s and 1’s.

For each string given in the input, output either “WIN m”, without quotes, if Pranjali can force her win in “m” scans in an optimal play, or output “INFINITE PLAY” if the game cannot be reached to the above mentioned goal in an optimal play.