A cat is chasing a mouse in a rectangular room which contains some obstacles. The cat and mouse move according to the following rules:

1. The cat and mouse move in turns, in alternating fashion. The cat starts.
2. Both the cat and the mouse can only move to a location that does not contain an obstacle, and that is horizontally, vertically, or diagonally adjacent to their current location. Staying in the same location is always a valid move.
3. Neither the cat nor the mouse can move beyond the border of the room.
4. The cat is always aware of the location of the mouse, and vice versa.

Given the description of the room, and the starting positions of the cat and of the mouse, your task is to decide whether the mouse can avoid the cat forever or not.

Input

The first line of the input contains T (1 ≤ T ≤ 10), the number of test cases. Then T test cases follow, separated by blank lines. Each test case consists of a line describing the length of the two sides of the room, R and C (1 ≤ R ≤ 10, 1 ≤ C ≤ 10), followed by a description of the room. The room is given as a matrix of R rows and C columns, where each entry of the matrix is either:

• a dot (.), if the corresponding location is free of obstacles,
• a hash sign (#), if the corresponding location contains an obstacle,
• an m, if the corresponding location is the starting position of the mouse,
• a c, if the corresponding location is the starting position of the cat.

The starting position of the cat and the starting position of the mouse are always different. Clearly, the starting positions are free of obstacles.

Output

The output consists of one line for each test case, containing the string mouse if the mouse can avoid the cat forever, and the string cat otherwise.

Example

Input:

2
3 3
#c#
.#m
#.#

3 3
#c#
.#.
#m#

Output

cat
mouse