题目描述

鸭哥拿到了一个仅包含小写字母的字符串$s$。对于每个下标$p$，如果$p$的二进制表示有奇数个$1$，那么将$s_p$修改为对应的大写字母。(下标从$1$开始)

例如，字符串"abcdefg"，其中下标$1、2、4、7$在二进制表示下都有奇数个$1$，因此字符串为"ABcDefG"。

鸭哥想知道她拿到的字符串修改是什么，你能帮帮她吗?

输入描述

第一行为输入一个整数$t(1\le t\le 2000)$，表示有$t$组输入。

接下来$t$行，每行一个仅包含小写字母的字符串$s(1\le |s|\le 500)$。

输出描述

输出$t$行，每行一个字符串，表示修改后的字符串。

样例1

输入

1
abcdefg

输出

ABcDefG

样例2

输入

3
vwcvnwaomy
ovoxcfdtf
yynbve

输出

VWcVnwAOmy
OVoXcfDTf
YYnBve