A. Security
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The head of information security department of a large corporation thinks it's about time he changed the passwords on all computers used by the corporation. The characters which are used in the old passwords and can be used in the new passwords are:

  • lowercase Latin letters;
  • uppercase Latin letters;
  • digits.

You have to write the program that, given the old password $$$s$$$ and the required length of the new password $$$k$$$, generates a new password according to the following constraints:

  • the new password should consist of exactly $$$k$$$ characters;
  • all characters of the new password should be different (same Latin letters in different cases are considered different, for example, 'a' and 'A' are different characters);
  • if a character appears in the old password, it should not appear in the new one.

If it is impossible to generate a new password according to these constraints, your program should report it.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of three lines:

  • the first line contains one integer $$$k$$$ ($$$1 \le k \le 62$$$) — the desired length of the new password;
  • the second line contains one integer $$$n$$$ ($$$1 \le n \le 62$$$) — the length of the old password;
  • the third line contains one string $$$s$$$ ($$$|s| = n$$$) — the old password, consisting of lowercase Latin letters, uppercase Latin letters, and/or digits. Note that there can be repeated characters in the old password.
Output

For each test case, print the answer on a separate line as follows:

  • if it is impossible to generate a new password, print a single hyphen (character '-' with ASCII code 45);
  • otherwise, print the new password. If there are multiple possible passwords, you can print any of them.
Example
Input
5
10
24
makethenewpasswordstrong
60
3
abc
13
6
xyzuvw
31
32
0aa1b2c3d4efghijklmABCDEFGHIJKLM
31
32
0a1b2c3d4e5fghijklmABCDEFGHIJKLM
Output
1234567890
-
donthackmepls
6789NzOyPxQwRvSuTtUsVrWqXpYoZn5
-