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:

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

Input

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 ('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. The length of the sequence will be no more than 300.

Output

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, starting with the most significant digit. The converted number mustn't have any unnecesary leading zeroes.

Sample Input

4
b 101
a 0
a 1111
b 1111
Sample Output
a 1 1 1
b 0
b 1 0 1 0
a 1 0 0 0