Hide

Problem E
Party Game

/problems/partygame/file/statement/en/img-0001.jpg
Image by Bain News Service (Wikimedia Commons), Public Domain

Lord Kevin (purportedly a distant relative of Lord Kelvin) is holding a party to celebrate his recent entrance into the British nobility. The exact process whereby Kevin acquired his title is a matter of some dispute, and there are even whispered rumours of identity theft, but fortunately we need not concern ourselves with such unpleasantries here. All the invitees to Kevin’s party are British Lords with whom he hopes to ingratiate himself, and since Kevin has detected that these nobles are a rather reserved lot, he has invented a party game to facilitate interactions among his guests. As the Lords arrive at Kevin’s manor, they are numbered from $1$ to $n$. Each Lord is given a lapel pin on which is written his unique identifying number, and he is asked to wear this pin throughout the evening. (Kevin, who is organizing the game but not participating in it, does not have an assigned number.) Once all the guests have assembled in the ballroom, Kevin takes a set of $n$ cards on which are written the numbers $1$ through $n$ (one number per card), places them in his top hat, and then draws them out at random and distributes them to his guests, one per Lord. Now the party game is ready to begin.

The game consists of a sequence of rounds, each of which has three stages. In Stage $1$, Kevin calls out “Match!”, at which point each Lord checks to see if the number on the card in his hand matches the number on his lapel pin. If so, the Lord is freed from the game and can move into the dining room to partake of the fine food (and drink) waiting there. In Stage $2$, Kevin calls out “Hat!”, at which point each remaining Lord memorizes the number on the card in his hand, and then places the card in the brim of his top hat. In Stage $3$, Kevin calls out “Snatch!”, at which point each Lord finds the other guest in the room whose lapel pin contains the number he has just memorized, and then snatches (or, more politely, gently takes) the card from that Lord’s hat. (Since British nobles are also called peers, Stage $3$ is an example of a peer-to-peer protocol.) At the end of Stage 3, each Lord once again has a numbered card in his hand, ready for the next round to begin. Note that at the end of Stage $1$, if all Lords have been freed from the game, the game is over, so obviously Kevin will skip the final Stages $2$ and $3$.

Kevin thinks that this game he has invented will be very fun for his guests, but he is a little worried that some of the Lords might stay trapped in the game forever, eventually dying of starvation. Given the initial distribution of numbered cards to guests, help Kevin determine whether or not the game will have such a dire outcome.

Input

The first line of input contains a single integer $T$ $(1 \leq T \leq 10)$, the number of test cases that follow. Each test case occupies two lines. The first line contains an integer $n$ $(1 \leq n \leq 1\, 200)$, the number of guests at the party. The second line contains $n$ distinct space-separated integers $a_1, a_2, \ldots , a_ n$, where $a_ i$ $(1 \leq i \leq n)$ is the number on the card initially given to the Lord whose lapel pin contains the number $i$.

Output

The output consists of $T$ lines, one per case. For each test case, output “All can eat.” if the game eventually ends, or “Some starve.” if the game never ends.

Sample Input 1 Sample Output 1
3
3
1 2 3
4
3 4 2 1
5
5 4 1 2 3
All can eat.
All can eat.
Some starve.

Please log in to submit a solution to this problem

Log in