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:
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:
If it is impossible to generate a new password according to these constraints, your program should report it.
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:
For each test case, print the answer on a separate line as follows:
51024makethenewpasswordstrong603abc136xyzuvw31320aa1b2c3d4efghijklmABCDEFGHIJKLM31320a1b2c3d4e5fghijklmABCDEFGHIJKLM
1234567890 - donthackmepls 6789NzOyPxQwRvSuTtUsVrWqXpYoZn5 -