Blurbish, a new number system, is used in Blurbland. This number system is in the decimal system we normally use. But her friends in Blurbland want to play a game with Berf, and they write the numbers using letters from the first letter of the alphabet (a) to the 10th letter (j). Also, different letters can correspond to the same number in the decimal system, but different digits must be encoded with different letters. Her friends don't tell Berf the numbers these letters correspond to in the decimal system and play a game with her.

The Blurbians give 3 distinct prime numbers less than 20 and \(\mathbf{N}\) numbers to Berf. They ask Berf whether these \(\mathbf{N}\) numbers can be divided by the product of the 3 prime numbers they give. If it is divisible, they also ask Berf to find the smallest positive integer that can correspond to this number in the normal decimal system. Can you help Berf?

Input

The first row contains 3 distinct prime numbers \(\mathbf{A}\), \(\mathbf{B}\) and, \(\mathbf{C}\).

The second line contains \(\mathbf{N}\), how many numbers in total are asked.

The next \(\mathbf{N}\) row contains a Blurbish number of up to 6 digits each.

• \(1 \leq \mathbf{A}, \mathbf{B}, \mathbf{C} \leq 20\)
• \(1 \leq \mathbf{N} \leq 10^{3}\)

Output

In total \(\mathbf{N}\) rows, the smallest positive decimal integer corresponding to each Blurbish number will be printed. If there is no corresponding number in the decimal system, "-1" will be printed.

Example

Input:

2 3 5
4
ab
abc
abab
aaaa

Output:

30
120
3030
-1

Input:

11 5 2
5
gjdhe
cfe
eed
higii
dbe

Output:

10010
110
110
20900
110

Explanation

• In Input 1.1, the smallest positive integer that can be encoded as "ab" in Blurbish is 30. ("a" is 3 and "b" is 0)
• In Input 1.2, the smallest positive integer that can be encoded as "abc" in Blurbish is 120. ("a" is 1, "b" is 2 and "c" is 0)
• In Input 1.3, the smallest positive integer that can be encoded as "abab" in Blurbish is 3030. ("a" is 3 and "b" is 0)
• In Input 1.4, there are no integers that can be divided by 2, 3, and 5 and can be encoded as "aaaa" in Blurbish.