The Game of Euler is played between two players on a 4x4 board. The board is initially empty. The players alternatively put pins of different lengths on the board. You can either put them from one of the sides, in which case the pin will cover the same number of squares as the length of the pin (1, 2 or 3), or you can put it perpendicular to the board (pushing it straight down), covering exactly 1 square. A pin may only cover squares that are not covered already. The player who puts the last pin, and thus makes all 16 squares covered, loses. Both players have an infinite supply of pins of length 1, 2 and 3.
Consider the position in the picture to the right. If the player to move covers one of the two squares in either corner, the opponent will cover both squares in the opposite corner, so the first player will have only one move and will thus lose. But if the first player covers both squares in one corner, the opponent will cover only one square in the other corner, winning again. So the first player will lose the game no matter what move he makes. We say that such a position is losing for the player to move, because no matter which move he makes, he will lose the game if the opponent plays "perfectly" (that is, make the best moves). If the position is not losing, it is winning. Since fewer and fewer squares remains uncovered as the play progresses, the game will always end with a loser and a winner (never a draw).
The first line in the input contains an integer N the number of test cases to follow (N < 100,000). Each test case contains of 4 lines, each line containing four character. These lines represent which squares of the board have been covered so far. A covered square is indicated by a 'X', an uncovered square is indicated by a '.'. At least one square on the board will be uncovered. Each test case is preceded by a blank line.
For each test case output a single line containing either "LOSING" or "WINNING" depending on whether the position is losing or winning for the player to move.
Finaly, some "history" about the Game of Euler. It contains no information vital for solving the problem, so you may skip it if you want.
"The origin of
the game is hidden in a distant past. One does know that it was used in ancient
philosophers of ancient
Knowledge of the
deeper meaning of the game and insights on how to play to win were the criteria used to qualify for membership in a group
called The Wise Men. The group never became larger than seven and it came to be
known as The Seven Wise Men. After the decline of
Next time the
game surfaces is during the plundering of Montezuma I's tomb in Tenochtitlán. The
Conquistadors led by Hernan Cortez discovered a
pierced block made of solid gold. The block's function was never understood and
it was melted together with the rest of the gold. We know this today because the
soldier who discovered the block Juan Rodriguez, was so
intrigued by it that he made notes on its form and size. The block departed from
all the other loot, both in form and function. Juan was the only person to be
spared the very painful stomach disease that eventually killed all other
conquistadors that had touched the block. The stomach pain became known as
Montezuma's revenge. The notes were passed on from generation to generation in
the Rodriguez family before they were made public. Even more remarkable is the
fact that the dimensions of the Aztec block exactly matches the dimensions used
The game remained unknown until Leonhard Euler reinvented the game. It is believed that
knowledge of the game could have survived from classical antiquity in certain
very secret orders, possibly among the Rosenkreutz and
probably in another even more secret order. The name of this group is not known
to this day and its existence is still disputed. Theory has it that the society
can trace its roots to the Nubians, a people that lived by the water of the
The society can
be traced in the Egyptian kingdom before it reaches
The order is led
by a person called the Head. Only the sharpest and wisest brains can be selected
for membership. Nothing indicates that the purpose of the group should be
anything but good. Its probable cause is to further the development of the human
species. Some say that Leonhard Euler was a member and
that by revealing the game he was excluded. It is believed that both
Neumann was probably the best player of all times if you exclude the best of the Yanco tribe. The Yanco tribe was discovered to the rest of the world by anthropologist Franz Boas. The tribe lives in the inner of the Amazons. The Yanco people have a game that is very similar to the classical but their game has 6x6, 7x7 or even up to 10x10 units. The Yancos unsurpassed skill is based solely on intuition. Their counting ability is low; the number three in Yanco language is called poettarraroincoaroac. Researchers that have visited the Yanco say that the number four is met by expressions of total confusion. They call the game Maua-maui, the dream-game and only the elders are allowed to play. To the other members it is taboo. The game is only used under religious ceremonies and the playing is preceded by complicated rituals to appease the game God.
All these stories about the game and the society could be pure imagination. It might be yet another trivial game and maybe not..."