Problem F - Pre, in and post

Time Limit: 1 second

A common problem in data structures is to determine the traversal of a binary tree. There are three classic ways to do it:

Pre-order: You must visit in sequence the root, left subtree and the right subtree.
In-order: You must visit in sequence the left subtree, the root and the right subtree.
Post-order: You must visit in sequence the left subtree, the right subtree and the root.

See the picture below:

The pre, in and post-order traversal are, respectively,  ABCDEF, CBAEDF and CBEFDA. In this problem, you must compute the post-order traversal of a binary tree given its in-order and pre-order traversals.

Input

The input set consists of a positive number C ≤ 2000, that gives the number of test cases and C lines, one for each test case. Each test case starts with a number 1 ≤ N ≤ 52, the number of nodes in this binary tree. After, there will be two strings S₁ and S₂ that describe the pre-order and in-order traversal of the tree. The nodes of the tree are labeled with different characters in the range a..z and A..Z. The values of N, S₁ and S₂ are separeted by a blank space.

Output

For each input set, you should output a line containing the post-order transversal for the current tree.

Sample input

3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF

Sample output

Yzx
cba
CBEFDA

您可能對以下文章有興趣

[UVA][Easy] 12614 - Earn For Future

[UVA][MST] 1235 - Anti Brute Force Lock

[UVA] 10938 - Flea circus

[UVA][greedy] 10570 - Meeting with Aliens