A Máquina de Turing

O ano é 1940. A Segunda Guerra Mundial está no auge, e os nazistas utilizam a máquina Enigma para cifrar todas as suas comunicações militares. O matematicista britânico Alan Turing e sua equipe em Bletchley Park trabalham incansavelmente para decifrar essas mensagens e mudar o rumo da guerra.

Uma das técnicas mais antigas e simples de cifragem é a Cifra de César, usada como pré-processamento em alguns protocolos de comunicação inimigos. Nela, cada letra do alfabeto é deslocada por um número fixo de posições. Por exemplo, com deslocamento 3: A→D, B→E, ..., Z→C.

Alan descobriu que todas as mensagens cifradas com esta técnica terminam sempre com um sufixo fixo de identificação de 8 caracteres — após a decifragem correta, os últimos 8 caracteres da mensagem sempre formam a string BLETCHLY (um código interno de autenticação). Sua tarefa é ajudar Alan a automatizar a decifração dessas mensagens.

Dado o texto cifrado, encontre o deslocamento correto da Cifra de César tal que, ao decifrar a mensagem, os últimos 8 caracteres formem exatamente BLETCHLY. Com o deslocamento encontrado, imprima a mensagem completamente decifrada.

Detalhes da cifra

• Apenas letras maiúsculas (A–Z) são cifradas. Outros caracteres (espaços, pontuação, dígitos) permanecem inalterados.
• O deslocamento $k$ satisfaz $0 \le k \le 25$. Decifrar significa subtrair $k$ (com wraparound): letra cifrada $c$ vira $((c - \text{'A'}) - k + 26) \bmod 26 + \text{'A'}$.
• É garantido que exatamente um valor de $k$ produz BLETCHLY nos últimos 8 caracteres da mensagem decifrada.

A entrada consiste em múltiplos casos de teste.

A primeira linha contém um inteiro $T$ $(1 \le T \le 100)$ — o número de casos de teste.

Cada caso de teste consiste em uma única linha contendo a mensagem cifrada — uma string com pelo menos 8 caracteres, contendo apenas letras maiúsculas e espaços. O comprimento da mensagem é no máximo $10^4$ caracteres.

Para cada caso de teste, imprima a mensagem decifrada em uma linha.