401574: GYM100495 F Snake++

Everybody knows video game called "Snake". Martynas is developing an upgraded version of the original – "Snake++".

This is the game mechanics:

• The field is rectangle, consisting of n × m squares.
• Snake is made of head and remaining body parts. Head is steering and body parts follow the head. The length of a snake is the number of its segments (body parts plus head).
• There is a single square, called pit, which is the starting position of the snake. At the beginning snakes head is above the ground and her body parts are in the pit below the ground. Step by step snake moves out of the pit (see the picture below). Snake is considered to leave the pit when every snake's segment occupies different square on the grid.
• Snake moves exactly the same as in the original game: from one square to adjacent one. Snake cannot occupy a square which is already occupied by other body part of itself.
• There are obstacles in some squares of the field. Snake cannot occupy these squares.
• All the pieces of food are placed in the field at the start of the game. After occupying a square with food snake's length increases (see the picture below).
• Snake can cross the boundaries of the field. That means going through the top of the field and appearing at the bottom (same for left and right boundaries).
• There can be no more than 5 pieces of food on the field.

An example of snake's, whose starting length is 4, movement is showed in the following image (black squares are obstacles, gray squares are snake, black dot is food). In the fourth step snake have came out of the pit (you can see 4 segments of snake).

Martynas has generated some fields. The problem is that some fields are too small — snake cannot leave the pit without hitting the wall or itself. Your job is to find if the field is too small or not.

The first line contains the number of test cases T (T ≤ 50). In the first line of every test case there are integers n, m and k (3 ≤ n, m ≤ 10, 2 ≤ k ≤ 5) – the height of the field, the width of the field and the starting length of the snake. In every following n lines there are m symbols: 'x' for starting pit, '#' for obstacle, little letter 'o' for food and dot '.' for unoccupied square.

For each test case output one line containing “Case #tc: fit”, where tc is the number of the test case (starting from 1) and fit is text "Fits perfectly!" (without quotes) if snake can leave the pit and "Oh no, snake's too fat!" otherwise.

2
3 5 5
#####
.x#..
###.#
3 5 5
#####
.x#o.
###.#

Case #1: Fits perfectly!
Case #2: Oh no, snake's too fat!