Background

Bajtek and Bitek are brothers (Bajtek is the older one), and they want to play a game.

Problem Description

The rules are: whoever writes the larger number wins.

Suppose Bajtek writes $A$, and Bitek writes $B$. $A$ and $B$ have the same length, and they may have leading zeros.

However, Bajtek wins every time (that is, always $A \ge B$), so Bajtek wants to lose once.

Now he can change exactly $k$ digits of $A$ so that $A$ becomes smaller than $B$.

Find the maximum possible value of $A$ after modification such that $A < B$.

If it is impossible to make $A$ smaller than $B$, output -1.

Because the brothers really like this game, they will play $t$ rounds, meaning there will be $t$ modifications and checks.

Input Format

The first line contains an integer $t$, the number of rounds.
The next $t$ lines each contain three integers $A, B, k$, representing the number written by Bajtek, the number written by Bitek, and the allowed number of modifications.

Output Format

Output $t$ lines, each containing one integer: the maximum value of $A$ after modification such that $A < B$.
If no modification of $A$ can make it smaller than $B$, output -1.

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

255
0499
-1
8

Hint

Sample Explanation

The first two additional samples correspond to sample1/2.in and sample1/2.out in the additional files.

The third additional sample is sample3.zip.

Constraints

This problem uses bundled testdata.

Let $n$ be the length of $A$ and $B$:

• Subtask 1 (18 pts): $1 \le n \le 5$.
• Subtask 2 (20 pts): $1 \le n \le 5000$.
• Subtask 3 (20 pts): $1 \le n \le 10^5$, $k = 1$.
• Subtask 4 (42 pts): no special constraints.

For $100\%$ of the testdata, $1 \le t \le 100$, $1 \le k \le n \le 10^5$, and $A \ge B$.

Notes

Translated from POI 2019 C Pomniejszenie。

Translated by ChatGPT 5