Problem F
Game of Euler
Input: Standard Input

Output: Standard Output

Time Limit: 3 Seconds

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).

Input

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.

Output

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.

Sample Input Output for Sample Input

3 XXX. XXX. .XXX .XXX XXXX ...X XX.X XX.X .... .... .... ....

LOSING WINNING LOSING

---

Problemsetter: Jimmy Mårdell, Member of Elite Problemsetters' Panel

History

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 Greece, especially in Athens was it very popular. Chess on the other hand was seen by the Athenians as undemocratic and warlike, a game for Spartans. The only reason the Spartans were so interested in chess was probably its use when training strategy for their constant war games. They had actually exchanged the queen for yet another king, since it was unthinkable in the patriarchal Spartan society to have a queen with more power than the king.

Many philosophers of ancient Greece discussed and wrote about the game, they covered subjects such as openings, endgames and its relation to mathematics. According to Kallimachos the game had its own department at the library in Alexandria. Despite the large amount of literature on the game none of these works have been found. All that has been found are indirect references, the most interesting is probably a note in a margin where Pythagoras claims to have found a very short proof, stating that the person making the first move is doomed to loose. This is remarkable since even to this day there is no proof for this that isn't based on an examination of all possible positions in the game. That Pythagoras really had a proof is indicated by the magic significance he gave to the numbers 1170, 2053 and 2602.

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 Greece the criteria were forgotten as the game itself, and it was never adopted by the Romans.

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 in ancient Greece.

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 Nile. The Nubians played the game by drawing with sticks in the sand. An archaeological expedition to the village of Ez in 1973 found petrified clay that shows the game in a frozen moment with five free positions remaining. Nearby petrified footsteps indicates that the game had been abruptly interrupted by an approaching crocodile. This took place several thousand years before the Egyptians would rise from the shadows of history.

The society can be traced in the Egyptian kingdom before it reaches Mesopotamia and the Sumerians and later the Babylonians. Its presence can be seen in western Anatolia where it probably recruits its members among the Pre-Socratic philosophers. Whether the society has followed the path of historical development and taken root in one civilisation after the other or if the society's capacity to influence has been so strong that it controlled the development are matters on which we can only speculate.

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 Newton and Galilei were Heads. Whether the society exists today is not known, apart from members if any. Some think that John von Neumann and Friedrich von Hayek were heads. One story tells that John von Neumann was inspired to his game theory during a game of Euler.

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..."