SPOJ Brasil

Sete Mares é um jogo divertido onde você é o capitão do navio de guerra. Você está no meio do oceano e há alguns navios inimigos que querem lhe capturar. Sua missão é fugir dos seus inimigos. Destrua-os se você puder!

O jogo é jogado em um tabuleiro de 9x8 e você pode se mover em todas as 8 direções, um passo a cada vez. Você move primeiro e os navios inimigos se movem em seguida. Os navios inimigos são muito estúpidos, de modo que eles sempre irão se mover para a posição mais próxima de você que eles puderem, mesmo se aquela posição destruir o navio deles. Um navio é destruído quando ele se move para uma célula que contém uma rocha. Se dois navios inimigos movem-se para a mesma célula então eles também serão destruídos e seus restos irão ficar naquela célula, de modo que se outro navio tentar ir para aquela célulua ele será destruído também.

Se um navio inimigo lhe alcançar, você morre e o jogo acaba.

Entrada

A primeira linha da entrada contém o número de cenários. Cada cenário consiste de um tabuleiro de 9x8 caracteres. Seu navio é representado por um 'S' no tabuleiro e os navios inimigos são representados por um 'E'. As rochas são representadas por um '#' e os '.' representam o mar. Veja o exemplo de entrada para conferir o formato de entrada específico.

Haverá no mínimo um e no máximo nove navios inimigos. Haverá uma linha em branco entre dois cenários.

Saída

Para cada cenário você deve descobrir se é possível destruir todos os navios inimigos em menos do que 10 passos. Se este é o caso, você imprimir uma linha com a cadeia: I'm the king of the Seven Seas!. Caso contrário, você deve imprimir uma linha com a cadeia: Oh no! I'm a dead man!.

Exemplo

Entrada:
3
........
.E.#....
...E....
..#.....
........
........
..S.....
........
........

........
.E.E....
...S....
.E..E...
........
........
........
........
........

E......#
........
........
........
........
........
........
.......S
#.......

Saída:
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!