[入门赛 #11] [yLOI2021] 扶苏与 1 (Hard Version)

**本题与 Easy Version 的区别是：$x$ 的范围不同，$y$ 的长度限制不同**。 **请注意 Easy Version 和 Hard Version 不是严格的包含关系。** 扶苏在 ICPC2022 EC Final 的比赛里，开局不到五分钟，就读假了一道题，把一道数位 DP 开成了简单签到，狠狠地演了队友一把。 为了不让读假了的题被浪费，所以这道题出现在了这里。

扶苏给了你一个数字 $x$，你需要给她一个数字 $y$，使得在列竖式计算 $x + y$ 时，能恰好产生 $k$ 个进位。 **你给出的 $y$ 的长度不能超过 $x$ 的长度。**（注意，这条要求与 Easy Version 不同） **进位**的含义是：在进行竖式加法运算时，如果位于同一列上的数字之和（加上低位向上可能存在的进位）比 $9$ 大，则在结果的这一列上只保留这个和的个位数字，同时称这一位向它的高位产生了一个**进位**。 下图是一个竖式加法的例子，结果中标红的两位都向上产生了进位。 

**本题单测试点内有多组测试数据**。 第一行为一个整数 $T$，代表测试数据组数。 接下来 $T$ 组数据，每组数据只有两行，每行一个整数。 第一行的整数表示 $x$。 第二行的整数表示 $k$。

**本题采用 special judge 进行判题**。 对每组数据，输出一行一个整数，表示你给出的 $y$。 如果有多个满足要求的 $y$，你可以输出任何一个。但是必须保证如下三条限制： - $y$ 是正整数。 - $y$ 不含前导 $0$。 - $y$ 的长度不超过 $x$ 的长度。 特别的，如果这样的 $y$ 不存在，请你输出一行一个 $\texttt{-1}$。

5
1
1
14
1
514
2
1234
1
123456
6

9
8
516
7
877777

### 数据规模与约定 对全部的测试点，保证 $0 \leq x < 10^{(10^4)}$，$1 \leq T \leq 5000$，$1 \leq k \leq 1+\log_{10}\max(1,x)$。输入的 $x$ 不含前导 $0$。 ### 提示 输入的 $x$ 可能会很大。如果说 $x < 10^t$，则输入 $x$ 的**长度**不会超过 $t$。数据规模中式子 $k \leq 1 + \log_{10}\max(1,x) $ 的含义是：$k$ 不会超过 $x$ 的长度。