Do the Untwist

Cryptography studies methods of secret communication that transform a message (the plaintext) into a disguised form (the ciphertext) so that no one who sees the ciphertext can recover the plaintext except the intended recipient. Turning the plaintext into the ciphertext is encryption; turning the ciphertext back into the plaintext is decryption. Twisting is a simple encryption method in which the sender and recipient agree in advance on a secret key $k$, a positive integer.

Twisting uses four arrays of length $n$, where $n$ is the length of the message: plaintext and ciphertext hold characters, while plaincode and ciphercode hold integers. All arrays are zero-indexed, so their elements are numbered from $0$ to $n-1$. Every message consists only of lowercase letters, the period, and the underscore (which stands for a space).

Given a key $k$, encryption proceeds as follows. First map each character of plaintext to an integer in plaincode using the rule

_ = 0, a = 1, b = 2, …, z = 26, . = 27.

Then compute each entry of ciphercode from plaincode: for every $i$ from $0$ to $n-1$,

$\text{ciphercode}[i] = (\text{plaincode}[k i \bmod n] - i) \bmod 28.$

Here $x \bmod y$ is the non-negative remainder of $x$ divided by $y$ (for example, $3 \bmod 7 = 3$, $22 \bmod 8 = 6$, and $-1 \bmod 28 = 27$). Finally, map the integers in ciphercode back to characters in ciphertext using the same rule as above; the result is the twisted message.

For example, twisting cat with key $5$ gives:

Your task is to untwist messages: given the key $k$, recover the original plaintext from the ciphertext. For instance, with key $5$ and ciphertext cs., your program must output the plaintext cat.

The input contains one or more test cases, followed by a line containing only the number $0$, which marks the end of the input. Each test case is on a line by itself and consists of the key $k$, a single space, and then a twisted message of at least $1$ and at most $70$ characters. The key $k$ is a positive integer no greater than $300$.

You may assume that untwisting a message always yields a unique result. (For readers familiar with number theory: this holds whenever the greatest common divisor of the key $k$ and the length $n$ equals $1$, which is guaranteed for every test case.)

For each test case, print the untwisted message on a line by itself.