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 
~2~ to count. However, Bob's computer needs to handle negative numbers as well, so instead, it uses base 
~-2~. Base ~-2~ is very similar to base ~2~, except the digits represent increasing powers of ~-2~ instead of ~2~. This means that the digits (from right to left) represent 
~1~, ~-2~, 
~4~, 
~-8~, and so on, instead of ~1~, ~2~, ~4~, 
~8~. However, there is still a problem: his computer can't convert between base ~-2~ and base 
~10~ yet. Can you help Bob write a program to do this?
There are two operations that will be needed:
A x Change 
~x~, a number in base ~-2~, into base ~10~.B y Change 
~y~, a number in base ~10~, into base ~-2~.
| Base -2 |
Conversion |
Base 10 |
 ~11011~ |
 ~(-2)^4 + (-2)^3 + (-2)^1 + (-2)^0~ |
 ~7~ |
 ~11010~ |
 ~(-2)^4 + (-2)^3 + (-2)^1~ |
 ~6~ |
Input Specification
The first line of input will contain 
~N~ 
~(1 \le N \le 1\,000)~, the number of operations to be performed.
The next ~N~ lines will each contain an operation in the format described above.
For at least 
~25\%~ of the marks, you will only need to convert from base ~-2~ to base ~10~.
For at least another ~25\%~ of the marks, 
~-10\,000 \le y \le 10\,000~.
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.