Osantu has been tagged as the best Bangladeshi contestant of present time by many and now he is mostly busy with the sweetest problem of his life — a baby boy. But Osantu often struggles to decode the sound that the baby makes throughout the year and so he asks for your help. He has converted the sound that the baby makes into a huge string. He thinks that sound made by the baby is often hard to understand because he replaces one character with another character. So in his diary he has prepared a list of replacement rules. Your job is to reverse these replacements and find the actual text that the baby wanted to say although in many cases the rules are not reversible. Input First line of the input file contains a positive integer T (T ≤ 6) which denotes how many test cases are there in the input file. The description of each test case is given below: First line of each test case contains a non-empty string S (containing only uppercase characters and underscore). The length of this string can be up to 1000000. Next line contains a positive integer R (R ≤ 10000), which denotes how many character replacement sequences follow. Each of the next R lines contains two characters ai and bi (both ai and bi are uppercase letters and separated by a single space) which denotes that while pronouncing the baby replaces character ai with character bi. As this replacement list is prepared by Osantu (who has short term memory) so the list can contain the same replacement rules twice, there can be cyclic rules like ‘A’ is replaced with ‘B’, ‘B’ is replaced with ‘C’ and ‘C’ is replaced with ‘A’ and also there can be contradicting rules like ‘A’ is replaced with ‘B’ and ‘A’ is replaced with ‘C’ etc. So what you simply need to do is apply the reverse of those rules in the order they appear in the input although it may not seem logical. Output For each set of input produce one line of output. This line contains the string that is found by applying all the R replacement rules. Illustration of the 2nd sample input: First replacement rule says the baby replaces ‘A’ with ‘B’. So to reverse that rule all ‘B’ s are replaced with ‘A’. So the string becomes “AAAACCY”. The 2nd rule says ‘B’ is replaced with ‘C’ and so to reverse this rule we replace all ‘C’s with ‘B’ and so the string becomes “AAAABBY”. The 3rd rule says that ‘C’ is replace with ‘A’ and so to reverse that we now replace all ‘A’s with ‘C’ and so the string finally becomes “CCCCBBY”. Sample Input 2 AVVU_TUMI_COLING_PARO_NAY 3 BV DL HY AABBCCY 3 AB BC
2/2 CA Sample Output ABBU_TUMI_CODING_PARO_NAH CCCCBBY