405078: GYM101775 L SOS

Mr. Panda and Mr. Sheep are playing a game on a 1 × N game board. Initially, all the cells are empty. Mr. Panda and Mr. Sheep take alternate moves and Mr.Panda moves first.

On each move, a player must fill an 'S' or 'O' into an empty cell. After the move, if there are 3 consecutive cells from left to right form the word "SOS", the player wins the game and the game finished.

If the board gets filled up without SOS appearing consecutively, no one wins the game, the game end with draw.

Now, if both Mr. Panda and Mr. Sheep play optimally, find out the result of the game.

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case contains one line consists of one number N, indicating the size of the game board.

• 1 ≤ T ≤ 1000.
• 1 ≤ N ≤ 1000.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the game result if both players play optimally. "Panda" for Mr. Panda winning the game, "Sheep" for Mr. Sheep winning the game, "Draw" for draw game.

2
3
7

Case #1: Draw
Case #2: Panda

In the first test case, as there are only 3 cells, both players cannot win as Mr. Sheep only has one move and after his move, there is still one cell left empty. So Mr. Sheep is impossible to win, but it's easy for him to avoid Mr. Panda to win. He can either fill 'O' in the first or third cell, or fill 'S' in the second cell to make it a draw game.