import java.util.*;

public class Main {
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int n;
        String entrada;
        String atalho[] = new String[15000];
        String saida = "";
        int k;
        int l = 0;
        n = in.nextInt();
        entrada = in.nextLine();
        String come;
        boolean achou;
        while(n>0){
            entrada = in.nextLine();
            k = in.nextInt();
            come = in.nextLine();
            saida = "";
            achou = false;
            if(k==0){
                System.out.println(entrada);
            }else{
                for(int i = 0;i<k;i++){
                    atalho[i] = in.nextLine();
                }
                for(int i = 0;i<entrada.length()-1;i++){
                    achou = false;
                    if(entrada.charAt(i)=='*'&&entrada.charAt(i+1)!='*'){
                        for(int j = 0;j<k;j++){
                            if(entrada.charAt(i+1)==atalho[j].charAt(0)){
                                saida+=atalho[j].substring(atalho[j].indexOf(" ")+1, atalho[j].length());
                                j=k;
                            }else if(j==k-1){//não existe o atalho
                                saida+=entrada.charAt(i);
                            }
                        }
                        i++;
                    }else{
                        saida+=entrada.charAt(i);
                    }
                }
                if(entrada.charAt(entrada.length()-2)!='*'){
                    saida+=entrada.charAt(entrada.length()-1);
                }
                System.out.println(saida);
            }
            n--;
        }
        in.close();
    }
}