## IPSC 2003

## Problem T – Strange Numbers

While searching for yet another forgotten civilization the
archaeologists have found some old writings. After a while they
realized that the writings are actually numbers. The ancient civilization
used only sequences of zeroes and ones (bits) to represent the numbers, but it
was not the ordinary binary system we use today.

The ancient number system works as follows: Zero is encoded as '0'. To
write the number (N+1) take the sequence for the number N and change
the least significant bit (1 to 0 and vice versa) such that the
sequence produced does not represent any number less than N. In case
no such bit exists prepend '1' to the sequence. The representation of
some numbers:

decimal binary ancient
0 0 0
1 1 1
2 10 11
3 11 10
4 100 110
5 101 111
6 110 101
15 1111 1000
16 10000 11000

Your task is to help the archaeologists to convert numbers from this
ancient system to binary and vice versa.

### Input file specification

The input file contains multiple test cases.
On the first line there is the number K of test cases. Each of the next K
lines of the input file contains one test case.

At the beginning of each of these lines there is a single character 'a'
or 'b' denoting the number system of the ('a' means the ancient number
system, 'b' means binary). On the rest of the
line there is a sequence of ones and zeroes encoding a number in the
given system.

### Output file specification

You have to process the test cases in the order in which they appear
in the input file. For each of the test cases, convert the number
from the input file to the other system. Write each converted number
formatted as follows:

At the beginning write one character 'a' or 'b' denoting the number system
of the converted number. (That is for every 'a' in the input file print 'b' and vice
versa.) Then write the digits of the converted number, separated by whitespaces
and starting with the most significant digit. The converted number mustn't
have any unnecesary leading zeroes.

Note that the number doesn't have to be printed on a single line.
To avoid problems with old mailers you may divide the digits into multiple
lines of the output file.

### Example

Input file:

4
b 101
a 0
a 1111
b 1111

Output file:

a 1 1 1
b 0
b 1 0
1 0
a 1 0 0 0