Vasya 想出了一个注册 EatForces 的密码——一个字符串 $$$s$$$。 EatForces 中的密码应该是一个字符串,由小写和大写拉丁字母和数字组成。
但由于 EatForces 注重用户的安全,因此用户密码必须包含至少一位数字、至少一个大写拉丁字母和至少一个小写拉丁字母。例如,密码“abaCABA12”、“Z7q”和“3R24m”有效,而密码“qwerty”、“qwerty12345”和“Password”则无效。
字符串 $$$s$$$ 的子字符串是字符串 $$$x = s_l s_{l + 1} \dots s_{l + len - 1} (1 \le l \le |s|, 0 \le len \le |s| - l + 1)$$$。 $$$len$$$ 是子字符串的长度。请注意,空字符串也被视为 $$$s$$$ 的子字符串,它的长度为 $$$0$$$。
然而,Vasya 的密码对于 EatForces 的安全设置来说可能太弱。他喜欢他的密码,所以他想用另一个相同长度的字符串替换它的一些子字符串,以满足上述条件。该操作应该只执行一次,并且所选字符串应该具有尽可能小的长度。
请注意,替换子字符串后,$$$s$$$ 的长度不应改变,并且字符串本身应仅包含小写和大写拉丁字母和数字。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 测试用例的数量。
接下来的$$$T$$$ 行包含初始密码$$$s~(3 \le |s| \le 100)$$$,由小写和大写拉丁字母和数字组成。
只允许 $$$T = 1$$$ 进行黑客攻击。
输出
对于每个测试用例,打印一个符合给定条件的更新密码。
被替换子串的长度计算如下:记下所有被更改的位置。如果没有,则长度为$$$0$$$。否则,长度是第一个和最后一个更改位置之间的差加一。例如,密码“abcdef”$$$\rightarrow$$$“a7cdEf”之间变化的子字符串长度为$$$4$$$,因为变化的位置是$$$2$$$和$$$5$$$,因此$$$(5 - 2) + 1 = 4$$$。
保证这样的密码始终存在。
如果有多个合适的密码 - 输出其中任何一个。
示例
输入 #1
2 abcDCE htQw27
输出 #1
abcD4E htQw27
注意
在第一个示例中,Vasya 的密码缺少数字,他将子字符串“C”替换为“4”,并获得密码“abcD4E”。也就是说,他改变了长度为1的子串。
在第二个示例中,Vasya 的密码从一开始就没有问题,无需更改任何内容。这与用另一个空子字符串(长度为 0)替换空子字符串相同。