CF1051A.Vasya And Password

Vasya came up with a password to register for EatForces — a string $s$. The password in EatForces should be a string, consisting of lowercase and uppercase Latin letters and digits.

But since EatForces takes care of the security of its users, user passwords must contain at least one digit, at least one uppercase Latin letter and at least one lowercase Latin letter. For example, the passwords "abaCABA12", "Z7q" and "3R24m" are valid, and the passwords "qwerty", "qwerty12345" and "Password" are not.

A substring of string $s$ is a string $x = s_l s_{l + 1} \dots s_{l + len - 1} (1 \le l \le |s|, 0 \le len \le |s| - l + 1)$. $len$ is the length of the substring. Note that the empty string is also considered a substring of $s$, it has the length $0$.

Vasya's password, however, may come too weak for the security settings of EatForces. He likes his password, so he wants to replace some its substring with another string of the same length in order to satisfy the above conditions. This operation should be performed exactly once, and the chosen string should have the minimal possible length.

Note that the length of $s$ should not change after the replacement of the substring, and the string itself should contain only lowercase and uppercase Latin letters and digits.

瓦西娅为注册 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$。

然而，瓦西娅的密码可能过于薄弱，无法满足 EatForces 的安全要求。他很喜欢自己的密码，因此希望恰好执行一次操作：将其中某个子串替换为另一个等长的字符串，使得新密码满足上述所有条件。该操作所替换的子串应具有尽可能小的长度。

注意：替换后字符串 $s$ 的总长度不得改变，且替换后得到的整个字符串仍只能由小写拉丁字母、大写拉丁字母和数字组成。

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of testcases.

Each of the next $T$ lines contains the initial password $s~(3 \le |s| \le 100)$, consisting of lowercase and uppercase Latin letters and digits.

Only $T = 1$ is allowed for hacks.

第一行包含一个整数 $T$（$1 \le T \le 100$）—— 表示测试用例的数量。

接下来的 $T$ 行中，每行包含一个初始密码 $s$（$3 \le |s| \le 100$），由小写和大写拉丁字母以及数字组成。

对于 hack，仅允许 $T = 1$。

For each testcase print a renewed password, which corresponds to given conditions.

The length of the replaced substring is calculated as following: write down all the changed positions. If there are none, then the length is $0$. Otherwise the length is the difference between the first and the last changed position plus one. For example, the length of the changed substring between the passwords "abcdef" $\rightarrow$ "a7cdEf" is $4$, because the changed positions are $2$ and $5$, thus $(5 - 2) + 1 = 4$.

It is guaranteed that such a password always exists.

If there are several suitable passwords — output any of them.

对每个测试用例，输出一个满足给定条件的新密码。

被替换子串的长度按如下方式计算：列出所有发生更改的位置。若没有位置发生更改，则长度为 $0$；否则，长度等于最后一个更改位置与第一个更改位置之差加一。例如，密码从 "abcdef" 变为 "a7cdEf" 时，更改的位置是 $2$ 和 $5$，因此被替换子串的长度为 $(5 - 2) + 1 = 4$。

保证这样的密码一定存在。

如果存在多个符合条件的密码，则输出其中任意一个即可。

In the first example Vasya's password lacks a digit, he replaces substring "C" with "4" and gets password "abcD4E". That means, he changed the substring of length 1.

In the second example Vasya's password is ok from the beginning, and nothing has to be changed. That is the same as replacing the empty substring with another empty substring (length 0).

在第一个例子中，瓦西娅的密码缺少一个数字，他将子串 “C” 替换为 “4”，从而得到密码 “abcD4E”。这意味着，他修改了一个长度为 1 的子串。

在第二个例子中，瓦西娅的密码从一开始就是合法的，因此无需任何修改。这等价于将一个空子串替换为另一个空子串（长度为 0）。