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 xChange ~x~, a number in base ~-2~, into base ~10~.
B yChange ~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~|
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)~.
For each operation, print out the result of the operation on a single line.
2 A 11011 B 6