PROGRAMMING:Xiao He's trip I
One day, Xiao He came to travel to a strange planet, but the coins here are printed with strange symbols and letters. Xiao He can't understand them, but he wants to buy something (if he doesn't eat, he will starve to death!), And you are the only person you know on that planet, so I asked you to translate for him.
Different races on the planet accept coins of different currencies, and the things Xiao He wants to buy come from shops opened by different races. Therefore, he wants to know what the value of his coins will be if he changes them into another kind of coins.
The coins over there have different denominations in different bases, and there are no Arabic numerals. They are only represented by * * lowercase letter * * and * * symbol * *. The letter represents the number, and the symbol represents its currency (that is, it represents several bases).
Symbol | represents
:--:|:--:
#|7-ARY
$| 17 system
^|Binary system
The corresponding table of letters and numbers is as follows:
The letter | stands for
:--:|:--:
a|0
b|1
c|2
...|...
j|9
k|10
l|11
...|...
For example, the value of a legal currency with the type of ＂ ABC ＂, ＂ BFA ＂.
###Enter a description
The first line contains only one integer, $$t (1 / Leq T / Leq 100) $, which indicates that there is an example of the $$t $$group.
The next $$t $$line contains a * * currency value * * and a target currency to be converted（ Data guarantee that there is no leading 0, that is, there is no such currency value starting with a as' # ABC ', and there will be no such currency value as 0 yuan** Ensure that the length of the currency value does not exceed 70, and the target currency is only 1 character
**Tip: the data range is large, please use long long type instead of int**
###Output description
Output the currency value of the target currency (leading 0 is not allowed).
###Input sample
```in
three
#bac ^
$bahdgm #
^bab #
```
###Output sample
```out
^bbaabb
#bfceaedg
#f
```
###Tips
Now change the input currency value into decimal system, and then convert< br>
answer：If there is no answer, please comment
Different races on the planet accept coins of different currencies, and the things Xiao He wants to buy come from shops opened by different races. Therefore, he wants to know what the value of his coins will be if he changes them into another kind of coins.
The coins over there have different denominations in different bases, and there are no Arabic numerals. They are only represented by * * lowercase letter * * and * * symbol * *. The letter represents the number, and the symbol represents its currency (that is, it represents several bases).
Symbol | represents
:--:|:--:
#|7-ARY
$| 17 system
^|Binary system
The corresponding table of letters and numbers is as follows:
The letter | stands for
:--:|:--:
a|0
b|1
c|2
...|...
j|9
k|10
l|11
...|...
For example, the value of a legal currency with the type of ＂ ABC ＂, ＂ BFA ＂.
###Enter a description
The first line contains only one integer, $$t (1 / Leq T / Leq 100) $, which indicates that there is an example of the $$t $$group.
The next $$t $$line contains a * * currency value * * and a target currency to be converted（ Data guarantee that there is no leading 0, that is, there is no such currency value starting with a as' # ABC ', and there will be no such currency value as 0 yuan** Ensure that the length of the currency value does not exceed 70, and the target currency is only 1 character
**Tip: the data range is large, please use long long type instead of int**
###Output description
Output the currency value of the target currency (leading 0 is not allowed).
###Input sample
```in
three
#bac ^
$bahdgm #
^bab #
```
###Output sample
```out
^bbaabb
#bfceaedg
#f
```
###Tips
Now change the input currency value into decimal system, and then convert< br>
answer：If there is no answer, please comment