P16877 [GKS 2022 #C] New Password

一家名为 Gooli 的公司发布了一项新政策，要求员工账户密码必须满足： 1. 至少包含 $7$ 个字符。 2. 至少包含一个大写英文字母。 3. 至少包含一个小写英文字母。 4. 至少包含一个数字。 5. 至少包含一个特殊字符。共有 $4$ 个特殊字符：`#`、`@`、`*` 和 `&`。 公司要求所有员工在密码不满足上述要求时进行更改。Charles 是 Gooli 的一名员工，他非常喜欢自己的旧密码。如果他的旧密码不满足上述要求，Charles 将通过添加字母、数字和特殊字符来修复它。你能帮助 Charles 找到满足公司要求的最短可能的新密码吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由 $2$ 行组成。每个测试用例的第一行包含一个整数 $N$，表示旧密码的长度。每个测试用例的第二行包含长度为 $N$ 的旧密码。旧密码仅包含数字、字母和特殊字符。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个有效的新密码，该密码通过可能修复旧密码的方式获得，并满足公司的要求。 保证至少存在一个解。如果有多个解，你可以输出其中任意一个。

在样例 #1 中，旧密码不满足要求 $2$、$3$ 和 $5$。一种可能的最短新密码是 `1234567aA&`。 在样例 #2 中，旧密码不满足要求 $2$、$3$ 和 $5$。一种可能的最短新密码是 `1111234567@Rc`。 ### 限制条件 $1 \le T \le 100$。 **测试集 1** $7 \le N \le 10^4$。 旧密码仅包含数字。 **测试集 2** $1 \le N \le 10^4$。 旧密码仅包含数字、字母和特殊字符。 翻译由 DeepSeek V4 Pro 完成