题目描述

梦幻学院最近经常出现学生账号被盗的情况，主要原因是大量学生设置的密码过于简单。

身为学院内最具智慧的小明，想出了一个解决方案：制定一套密码规则，提升密码的安全性，同时将现有不符合这套规则的学生密码进行批量更新

目前新的密码规则如下：

• 必须至少由 $7$ 个字符组成
• 必须至少含有 $1$ 个大写英文字母
• 必须至少含有 $1$ 个小写英文字母
• 必须至少含有 $1$ 个数字
• 必须至少含有 $1$ 个特殊字符。特殊字符只允许使用 #、@、*、& 这几种。

接下来就是批量修改不符合规则的密码了，梦幻打算让你帮忙设计一个程序，检测学生密码的规范性。假如学生密码符合上述规则，则不做处理；否则对密码进行修改。

为了学生便于记忆，梦幻希望在保留旧密码字符串的前提下，尽可能少的在末尾添加新字符来适配新的密码规则。

输入格式

第一行一个整数 $T$，表示共有 $T$ 组数据，每组数据格式如下：

第一行一个整数 $L$，表示旧密码的长度

第二行一个长度为 $L$ 的字符串（不含空格），表示旧密码。

输出格式

共 $T$ 行，每行对应一组数据的答案。

对于每一组数据，答案并不唯一，只需要输出任意一种符合题目要求的答案即可。

测试样例

2
4
2258
8
11112567

2258zA&
11112567c@K

3
1
B
2
3*
7
1234aB&

Ba1*439
3*zxCD*
1234aB&

数据范围

对于 $50\%$ 的数据，旧密码仅由数字组成，且 $7 \le L \le 10^4$。

对于 $100\%$ 的数据，$1 \le T \le 100, 1 \le L \le 10^4$，旧密码仅可能由大小写字母、数字、规定范围内的特殊字符组成。