P16877 [GKS 2022 #C] New Password

A company named Gooli has issued a new policy that their employees account passwords must contain: 1. At least $7$ characters. 2. At least one uppercase English alphabet letter. 3. At least one lowercase English alphabet letter. 4. At least one digit. 5. At least one special character. There are $4$ special characters: `#`, `@`, `*`, and `&`. The company has asked all the employees to change their passwords if the above requirements are not satisfied. Charles, an employee at Gooli, really likes his old password. In case his old password does not satisfy the above requirements, Charles will fix it by appending letters, digits, and special characters. Can you help Charles to find the shortest possible new password that satisfies his company's requirements?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of $2$ lines. The first line of each test case contains an integer $N$, denoting the length of the old password. The second line of each test case contains the old password of length $N$. Old password contains only digits, letters, and special characters.

For each test case, output one line containing `Case #`$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is a valid new password, obtained by possibly fixing the old password in the way that Charles wants and satisfying the company's requirements. It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them.

In Sample Case #1, the old password does not satisfy requirements $2$, $3$, and $5$. One possible shortest new password is 1234567aA&. In Sample Case #2, the old password does not satisfy requirements $2$, $3$, and $5$. One possible shortest new password is 1111234567@Rc. ### Limits $1 \le T \le 100$. **Test Set $1$** $7 \le N \le 10^4$. The old password contains only digits. **Test Set $2$** $1 \le N \le 10^4$. The old password contains only digits, letters, and special characters.