Type: Default 1000ms 256MiB

L3-1 内伐

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

高贵的名门袁绍有三个儿子,老大叫袁谭老二叫袁熙老三叫袁尚。袁绍死后由袁尚继承了袁绍的官位和爵位。对此,袁谭表示:“明明是我先来的……长子也好……继承权也好……”。于是本就不和的两兄弟彻底闹翻了,他们决定用一场比赛的输赢来决定最后的继承权。游戏规则为袁尚袁谭各写下一个数A、B,较大的一方获胜。本来袁尚写下的数总是要大一些,但是作为老大,袁谭总是有一些本领在身上的,他可以修改袁尚写下的数中的k位数字(必须修改共计k位数字),使得A<B,现在请你找到A修改后比B小的最大值,如果怎么改都无法达到目的,输出-1.因为老大有些耍赖,导致他们要比赛t局。

Format

Input

第一行一个数字t表示局数

接下来t行每行三个整数A,B,k表示袁尚写的数,袁谭写的数和k

用n表示A,B的位数,1<=k<=n<=1e5,1<=t<=100,B≤A

Output

t行数字,每行一个整数表示A修改后比B小的最大值,如果不能达到目的输出-1.

Samples

4
555 333 1
0555 0551 3
0555 0333 4
9 9 1
255
0499
-1
8

Limitation

1s, 1024KiB for each test case.