Decoding Coded Messages

During a fierce battle, the Pandavas need to exchange secret messages encoded with a unique system. Each message is encoded as a number by multiplying distinct prime numbers, each representing a lowercase English letter. Your task is to decode the message: given a mapping between characters and prime numbers and an encoded number M, factorize M using the provided primes. If each prime in the factorization appears exactly once and no extra factors remain, output the corresponding characters sorted in alphabetical order. Otherwise, output “Impossible”.

The encoding works as follows:

• Each character is associated with a unique prime number.
• A message is encoded by multiplying together the prime numbers corresponding to the characters in the message.
• The decoded message should list the characters in alphabetical order.

For example, if the mapping is: a→2, b→3, c→5 and M = 30, then since 30 = 2×3×5 the decoded message is "abc".

Additionally, the following constraints hold: (1 \le T \le 5)\quad (number of test cases) (1 \le N \le 26)\quad (number of mapping entries per test case) (2 \le M \le 10^{18})\quad (encoded number) All primes are distinct and lie between 2 and 1000.

inputFormat

Input is read from standard input (stdin). It begins with an integer T indicating the number of test cases. Each test case is structured as follows:

• An integer N representing the number of characters in the custom numbering system.
• N subsequent lines each containing a lowercase English letter and an integer (the prime number associated with that letter), separated by space.
• An integer M which is the encoded number to decode.

For example:

2 3 a 2 b 3 c 5 30 5 a 2 b 3 c 5 d 7 e 11 77

outputFormat

For each test case, output a single line to standard output (stdout) containing the decoded message. The decoded message should be the characters corresponding to the prime factors of M arranged in alphabetical order. If M cannot be factorized exactly into the provided primes (including cases where a prime factor appears more than once or extra factors persist), output “Impossible”.## sample

2
3
a 2
b 3
c 5
30
5
a 2
b 3
c 5
d 7
e 11
77

abc
de