题目内容

小塔拿到了一个仅包含小写字母的字符串$s$。

对于每个下标$p$，如果$p$的二进制表示有奇数个$1$，那么将$s_p$修改为对应的大写字母。(下标从$1$开始)

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

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

输入描述

第一行为$T$，表示有T组输入。

接下来$T$行，每行一个仅包含小写字母的字符串$s$。

$1≤T≤2000$

$1≤len(s) ≤500$

输出描述

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

样例1

输入

1
abcdefg

输出

ABcDefG

样例2

输入

3
vwcvnwaomy
ovoxcfdtf
yynbve

输出

VWcVnwAOmy
OVoXcfDTf
YYnBve