SPOJ Brasil

Bolhas ltda. está desenvolvendo uma nova tecnologia para navegar em um mapa com diferente niveis de ampliação. A nova tecnologia deles assume que uma região a ser mapeada é uma superficie plana retangular e divide esta superficie em sub-regiões retangulares, que representam níveis de ampliação mais profundos.

A tecnologia da Bolhas ltda. representa mapas usando uma estrutura conhecida como quad-tree. Em uma quad-tree, uma região retangular chamada x pode ser dividida na metade, tanto horizontalmente quanto verticalmente, resultando em quatro sub-regiões retangulares de mesmo tamanho. Estas sub-regiões são chamadas regiões filhas de x, e são nomeadas x_p para a região superior-esquerda, x_q para a região superior-direita, x_r para a região inferior-direita e x_s para a região inferior-esquerda, onde x_c representa a concatenação da string x com o caracter c = 'p', 'q', 'r' ou 's'. Por exemplo, se a região base a ser mapeada se chama m, as regiões filhas de m são, a partir do canto superior-esquerdo na ordem horária: m_p, m_q, m_r e m_s, como ilustrado a seguir.

Qualquer região pode ser subdividida novamente. Por exemplo, a região chamada m_s pode ser novamente dividida nas subregiões m_sp, m_sq, m_sr e m_ss, como ilustrado a seguir.

Um outro exemplo, a figura a seguir mostra o resultado da subdivisão das sub-regiões filhas da região chamada m_sr.

Sub-regiões com nomes de mesmo comprimento tem o mesmo nível de ampliação, desde que elas representem regiões de mesmo tamanho. Sub-regiões no mesmo nível de ampliação que compartilham um lado comum são ditas vizinhas.

Qualquer coisa que esteja fora da região base m não é mapeada e, para todos os niveis de ampliação, todas sub-regiões de m são mapeadas.

A tecnologia dos mapas bolha fornece um modo para o usuário navegar de uma dada sub-região para sub-regiões vizinhas nas direções cima, baixo, esquerda e direita. Sua missão é ajudar a Bolhas ltda. a encontrar as sub-regiões vizinhas de uma dada sub-região. Isto é, dado o nome de uma sub-região retangular, você deve determinar os nomes de suas quatro sub-regiões vizinhas.

Entrada

A entrada contém varios casos de teste. A primeira linha contém um inteiro N indicando o numero de casos de teste. Cada uma das N linhas seguintes representa um caso de teste, contendo o nome de uma região composta por C caracteres (2 <= C <= 5000), o primeiro sempre será a letra 'm' e os seguintes serão 'p', 'q','r' ou 's'.

Saída

Para cada caso de teste na entrada seu programa deve produzir uma linha na saida, contendo os nomes das quatro regiões vizinhas da região dada na ordem de direção cima, baixo, esquerda, direita. Para os vizinhos que não mapeados vode deve imprimir '<none>' ao invés de seu nome. Deixe um espaço em branco entre dois nomes consecutivos.

Exemplo de entrada 
2 
mrspr 
mps

Exemplo de saída 
mrspq mrssq mrsps mrsqs 
mpp msp <none> mpr