求二叉树的层次遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知一颗二叉树的前序遍历和中序遍历,求二叉树的层次遍历。

Input

输入数据有多组,输入T,代表有T组测试数据。每组数据有两个长度小于50的字符串,第一个字符串为前序遍历,第二个为中序遍历。

Output

每组输出这颗二叉树的层次遍历。

Sample Input

2
abc
bac
abdec
dbeac

Sample Output

abc
abcde

Hint

Source

fmh