Description

游戏规则为：写下较大数的人获胜。

假设 Bajtek 写的是 $A$，Bitek 写的是 $B$。$A$ 和 $B$ 的长度相等，且可能有前导零。

但是每次比赛都是 Bajtek 赢（即总是 $A \ge B$），所以 Bajtek 想输一次。

他现在可以修改 $A$ 上的 恰好 $k$ 位，使得 $A$ 比 $B$ 小。

求 $A$ 修改后比 $B$ 小的最大值。

如果无法使得 $A$ 比 $B$ 小，输出 -1。

因为兄弟俩很喜欢玩这个游戏，所以他们要玩 $t$ 局，即要进行 $t$ 次修改与判断。

Input Format

第一行一个整数 $t$ 代表局数。
接下来 $t$ 行每行三个整数 $A,B,k$ 代表 Bajtek 写的数，Bitek 写的数，和允许的修改次数。

Output Format

$t$ 行每行一个整数代表 $A$ 经过修改后比 $B$ 小的最大值。
如果 $A$ 怎样修改都不能使得 $A$ 比 $B$ 小，输出 -1。

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

255
0499
-1
8

Hint

样例说明

前两组附加样例分别对应附加文件中的 sample1/2.in 和 sample1/2.out。

第三组附加样例为 sample3.zip。

数据规模与约定

本题采用捆绑测试。

假设这里的 $n$ 为 $A,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）：无特殊限制。

对于 $100\%$ 的数据，$1 \le t \le 100$，$1 \le k \le n \le 10^5$，$A \ge B$。

说明

翻译自 POI 2019 C Pomniejszenie。