小红拿到了一个仅包含小写字母的字符串 ，下标从 开始。对于每个下标 ，如果 的二进制表示中 的个数是奇数，则将第 个字符转换成对应的大写字母。 请你对字符串 进行上述修改，并输出最终结果。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下： 输入一个长度为 ，仅包含小写字母的字符串 。

输出描述:

对于每一组测试数据，新起一行，输出修改后的字符串。