Alien Expression Evaluation

You are given arithmetic expressions in an alien language where each letter represents a digit. Your task is to decode each expression using the provided mapping and then evaluate it. The expression is composed of digits, spaces, and the following operators: \(+, -, \times, \div\). For every alphabetic character, replace it with its corresponding integer digit from the mapping, then compute the result using standard operator precedence.

The evaluation must follow the standard arithmetic rules: multiplication and division have higher precedence than addition and subtraction. There are no parentheses in the expressions.

Example:

Input Expression: a * b + c
Mapping: { 'a': 2, 'b': 3, 'c': 5 }
Decoded Expression: 2 * 3 + 5
Result: 11

inputFormat

The first line of input contains a single integer \(T\) representing the number of test cases. For each test case, the input is structured as follows:

1. A line containing the alien language expression as a string. The expression may include spaces and the arithmetic operators \(+, -, \times, \div\).
2. A line with an integer \(N\) indicating the number of key-value pairs in the mapping.
3. \(N\) lines each containing a lowercase letter and an integer (separated by a space) representing the mapping from that letter to its digit.

All input is read from standard input (stdin).

outputFormat

For each test case, output the evaluated result of the decoded expression on a separate line. The output should be printed to standard output (stdout).

## sample

3
a * b + c
3
a 2
b 3
c 5
x * y * z
3
x 4
y 8
z 16
p + q
2
p 14
q 12

11
512
26

</p>