Here you have to decipher the AMSCO cipher:

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 ciphertext. Ciphertext letters are in [A-Z] only with no punctuation. The keylength max is 9 and the length of the ciphertext is limited to 250. The last line ends with EOF.

Output

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

Example

Input:
7456321 HETEAMTTOWIMONNSEJNDTOSEBRERRHOOISSMIURNORISHIROR

Output:
RIDERSONTHESTORMINTOTHISHOUSEWEAREBORNJIMMORRISON

Input:
41325 CECRTEGLENPHPLUTNANTEIOMOWIRSITDDSINTNALINESAALEMHATGLRGR

Output:
INCOMPLETECOLUMNARWITHALTERNATINGSINGLELETTERSANDDIGRAPHS