Due to A.M. Scott in the 19th century, it's an incomplete columnar transposition cipher with alternating single letters and digraphs. The first entry must be a digraph. In both even and odd periods the first column and the first row always alternate:

Input

N lines (N < 1000) Each line of the input contains the numeric key (permutation order of the columns) and a plaintext. Plaintext letters are in [A-Z] only with no punctuation. The maximum keylength is 9 and the length of the plaintext is limited to 250. The last line ends with EOF.

Output

Output consist of exactly N lines of ciphertexts with letters in [A-Z] with no spaces.

Example

Input:
41325 INCOMPLETECOLUMNARWITHALTERNATINGSINGLELETTERSANDDIGRAPHS
Output:
CECRTEGLENPHPLUTNANTEIOMOWIRSITDDSINTNALINESAALEMHATGLRGR