High School Programming League Problems Archive

This week Johnny learned about binary trees, and he now wants to impress his girlfriend Anna. He has invented a cipher based on his knowledge of binary trees. Since his programming capabilities are very limited he has asked you for help.

To encode some text, which is n letters long, Johnny considers a complete binary tree of size n. It is a tree in which all leaf nodes are at depth d or d-1, for some value of d, and moreover all leaves at depth d are as far to the left as possible. Into each node of the tree Johnny then writes one letter of the text, level by level, starting from the top level, and from the left of each level. After that he chooses a preorder, inorder or postorder traversal of the tree and reads the text in that order.

For example, to encode the text ENCODETHIS, Johnny would build a tree with root E, nodes NC in the second level, ODET in the third level and HIS in the fourth level. Letters H and I would be the children of O, and S would be the left son of D. Reading this text according to the inorder traversal would give: HOINSDEECT.

Your task is to write a program which can encode, and decode texts using Johny's algorithm. Which tree ordering should be used will be specified at input each time.

Input

The first line contains an integer t <= 1000, denoting the number of testcases.

Each testcase consists of two lines, where the first line consists of a number 1 <= n <= 10000, the length of the text, and after spaces, one of the words PREORDER, INORDER or POSTORDER, followed by one of the words ENCODE or DECODE.

The second line of the testcase consists of n characters which are capital letters from the range 'A'..'Z'.

Output

You should output t lines, one for each testcase, with appropriately encoded or decoded text.

Example

Input:
8
10 INORDER ENCODE
ENCODETHIS
8 INORDER DECODE
FDEBDEAE
8 INORDER ENCODE
DEADBEEF
8 POSTORDER ENCODE
DEADBEEF
8 POSTORDER DECODE
DEADBEEF
8 PREORDER ENCODE
DEADBEEF
8 PREORDER DECODE
DEDFBAEE
14 POSTORDER DECODE
VENSAYONNLAOHJ

Output:
HOINSDEECT
DEADBEEF
FDEBDEAE
FDBEEEAD
FDEEABED
DEDFBAEE
DEADBEEF
JOHNYLOVESANNA

Scoring

By solving this problem you score 10 points.