题目描述

一家名为 Gooli 的公司发布了一项新政策，要求员工账户密码必须满足：

1. 至少包含 $7$ 个字符。
2. 至少包含一个大写英文字母。
3. 至少包含一个小写英文字母。
4. 至少包含一个数字。
5. 至少包含一个特殊字符。共有 $4$ 个特殊字符：#、@、* 和 &。

公司要求所有员工在密码不满足上述要求时进行更改。Charles 是 Gooli 的一名员工，他非常喜欢自己的旧密码。如果他的旧密码不满足上述要求，Charles 将通过添加字母、数字和特殊字符来修复它。你能帮助 Charles 找到满足公司要求的最短可能的新密码吗？

输入格式

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

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个有效的新密码，该密码通过可能修复旧密码的方式获得，并满足公司的要求。

保证至少存在一个解。如果有多个解，你可以输出其中任意一个。

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&

提示

在样例 #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 完成