Maximize Modified A for Losing Game

In this problem, you are given two numbers A and B of equal length (possibly with leading zeros) such that initially A \ge B. In each game, Bajtek (who usually wins) wants to lose by making A < B. To do so, he is allowed to modify exactly ( k ) digits in A. However, he wants to maximize the resulting number (i.e. get the largest possible modified A) while ensuring that the new A is strictly less than B. If it is impossible to obtain an A that is less than B by modifying exactly ( k ) digits, output -1.


Detailed description:
Let A and B be strings of digits of equal length, and let ( k ) be the number of digits you must change in A. A modification means picking a digit in A and replacing it with another digit (different from the original). The resulting number (with possible leading zeros) must satisfy ( A' < B ) (when compared lexicographically as numbers of equal length). Among all valid modifications, you need to find the one that maximizes A' (that is, the largest possible number satisfying ( A' < B )).

Note: It is guaranteed that in every game, initially ( A \ge B ), and you have to perform exactly ( k ) modifications.

inputFormat

The first line contains an integer ( t ) (( t \ge 1 )), the number of test cases. Each of the next ( t ) lines contains two strings A and B and an integer ( k ) separated by spaces, where A and B have the same length and consist of digits.

outputFormat

For each test case, output the maximum modified version of A that is strictly less than B after exactly ( k ) modifications. If it is impossible, print -1.

sample

3
321 123 1
456 456 2
100 100 1

021
449
000