【题目描述】

只由 0 和 1 组成的字符串称为比特字符串。

如果比特字符串中 1 的个数为奇数，则称它是奇性的；

如果 1 的个数为偶数，则称它是偶性的。

特别地，$0$ 是偶数，所以不包含 1 的比特字符串是偶性的。

每组数据给出一个比特字符串，并在末尾附加一个字母：e 表示希望最终字符串为偶性，o 表示希望最终字符串为奇性。

请把这个末尾字母替换成 0 或 1，使替换后的比特字符串满足要求。

【输入描述】

第一行输入整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行输入一组数据，由若干个 0、1 后跟一个小写字母 e 或 o 组成。

保证：

• $1\le T\le 1000$；
• 每组比特字符串部分长度在 $1$ 到 $31$ 之间；
• 末尾标记只可能为 e 或 o。

【输出描述】

对每组数据输出一行，为替换最后一个字母后的比特字符串。

【样例 1】

【样例 1 输入】

5
101e
010010o
1e
000e
110100101o

【样例 1 输出】

1010
0100101
11
0000
1101001010