Description

Source Problem: POI XXVII - I etap (Pomniejszenie)

Bytie and Bitie are playing a simple game – the person who writes down the greater number wins. The brothers already wrote their numbers on sheets of paper: Bytie wrote $A$ whereas Bitie $B$. Bytie, who is older and more experienced, always picks the larger number, but this time he wants to let his little brother win. So he peeked discretely at Bitie’s sheet and, knowing $B$ he wants to change exactly $k$ digits in his own number $A$ so that this yields a number smaller than $B$. To make it less discernible that he threw (i.e., intentionally lost) the game, Bytie wants to obtain the largest possible number that is less than $B$. Help him out in this task!

Input

In the first input line, there is a single positive integer $t$, specifying the number of game instances to consider.

Each of the $t$ lines that follow contains three nonnegative integers $A$, $B$, and $k$. The numbers $A$ and $B$ have the same length and may have leading zeros. The number k is positive and no larger than the (common) length of $A$ and $B$. Moreover, $A \geq B$.

Output

Exactly $t$ lines should be printed to the output, the $i$-th of which should hold the answer to the $i$-th instance from input. The answer for given $A$ and $B$ is the (single) integer $C$ such that:

• the number $C$ has the same length as $A$ and $B$ (and may have leading zeros),
• $C < B$,
• the number $C$ may be obtained from $A$ by changing exactly $k$ of its digits,
• $C$ is maximum subject to above constraints.

If there is no integer $C$ that satisfies these conditions, the number $−1$ should be printed.

4
555 333 1
0555 0551 3
0555 0333 4
9 9 1

255
0499
-1
8

Additional Samples

See files pom/pom*.in and pom/pom*.out for additional samples.

• Additional Sample 1: $t = 100$; $A$ equals $20 000, 20 001, \ldots$, whereas $B$ is constantly $20 000$; $k = 1$;

• Additional Sample 2: $t = 100$; in each test $n = 5000$ and the only digit appearing in either $A$ or $B$ (apart from leading zeros) is $9$; $k = 4901, \ldots , 5000$;

• Additional Sample 3: $t = 100$; in each test $n = 100 000$, the only digit (apart from leading zeros) appearing in $A$ is $9$, and the only one in $B$ is $2$; $k = 1, \ldots , 100$.

Constraints

The set of tests consists of the following subsets. Within each subset, there may be several tests. We denote the length of $A$ and $B$ by $n$.

All tests satisfy $1 \leq t \leq 100$.