Internet Problem Solving Contest

• Easy input data set – T1
• Hard input data set – T2

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