Bob is now so rich that he is no longer able to keep track of his own wealth. Instead, he now uses a computer to do it for him. Most computers use binary, or base to count. However, Bob's computer needs to handle negative numbers as well, so instead, it uses base . Base is very similar to base , except the digits represent increasing powers of instead of . This means that the digits (from right to left) represent , , , , and so on, instead of , , , . However, there is still a problem: his computer can't convert between base and base yet. Can you help Bob write a program to do this?

There are two operations that will be needed:

`A x`

Change , a number in base , into base .`B y`

Change , a number in base , into base .

Base -2 | Conversion | Base 10 |
---|---|---|

#### Input Specification

The first line of input will contain , the number of operations to be performed.

The next lines will each contain an operation in the format described above.

For at least of the marks, you will only need to convert from base to base .

For at least another of the marks, .

#### Output Specification

For each operation, print out the result of the operation on a single line.

#### Sample Input

```
2
A 11011
B 6
```

#### Sample Output

```
7
11010
```

## Comments

Is it guaranteed that converting to base -2 is always possible?

You may assume there is always a valid solution.