# 1194 - Prefixa, Infixa e Posfixa
- **ID**: 1194
- **IdBecrowd**: 1194
- **Tags**: estruturas-dados, grafos, strings
- **Nível**: 3
- **Tempo Limite**: 1 segundos
- **Memória**: 200 MB
- **Categoria**: Grafos
- **Autor**: Sebastião Alves Brasil, UNIP

## Descrição
Um problema comum em estrutura de dados é determinar o percurso transversal de uma árvore binária.

                    Há tres formas clássicas de fazer isto:

                    Prefixa: Você deve visitar a raiz, sub-árvore esquerda e sub-árvore direita.

                    Infixa: Você deve visitar a sub-árvore esquerda, a raiz e a sub-árvore direita.

                    Posfixa: Você deve visitar a sub-árvore esquerda, a sub-árvore direita e a raiz.

                    Veja a figura abaixo:
                

![](assets/images/8cdf6f_UOJ_1194.png)

                    O percurso prefixo, infixo e posfixo são, respectivamente ABCDEF, CBAEDF and CBEFDA. Neste problema, você deve computar a forma posfixa da árvore dados os percursos infixo e prefixo

## Entrada
A primeira linha de entrada contém um número positivo C (C ≤ 2000), que indica o número de casos de teste. Seguem C linhas, uma para cada caso de teste. Cada caso de teste inicia com um número N (1 ≤ N ≤ 52), o número de nodos da árvore binária. Depois haverá duas strings S1 e S2 que descrevem o percurso prefixo e infixo da árvore. Os nodos da árvore são nomeados com diferentes caracteres dentro do intervalo a..z e A..Z. O valor de N, S1 e S2 são separados por um espaço em branco.

## Saída
Para cada conjunto de entrada, você deve imprimir uma linha contendo o percurso posfixo da corrente árvore.

## Exemplos
### Exemplo de Entrada
```
3

                                3 xYz Yxz

                                3 abc cba

                                6 ABCDEF CBAEDF
```

### Exemplo de Saída
```
Yzx

                                cba

                                CBEFDA
```