题目描述

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.

2
7
1234567
10
1111234567

Case #1: 1234567aA&
Case #2: 1111234567@Rc

3
1
A
2
1*
7
1234aB&

Case #1: Aa1*111
Case #2: 1*abAA*
Case #3: 1234aB&

提示

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.