P9215 [Beginner Contest #11] [yLOI2021] Fusu and 1 (Hard Version)

**The difference between this problem and the Easy Version is: the range of $x$ is different, and the length limit of $y$ is different.** **Please note that the Easy Version and the Hard Version are not in a strict containment relationship.** In the contest ICPC2022 EC Final, within less than five minutes after the start, Fusu misread a problem, and turned a digit DP problem into an easy warm-up problem, completely tricking her teammates. To avoid wasting the misread problem, it appears here.

Fusu gives you a number $x$. You need to give her a number $y$ such that when performing the column addition $x + y$, it produces exactly $k$ carries. **The length of your $y$ must not exceed the length of $x$.** (Note that this requirement is different from the Easy Version.) The meaning of a **carry** is: in column addition, if the sum of the digits in the same column (plus any carry from the lower column) is greater than $9$, then only the ones digit of this sum is kept in this column of the result, and we say this digit generates a **carry** to the higher column. The picture below shows an example of column addition. The two digits marked in red in the result both generate carries upward. 

**There are multiple groups of testdata in a single test point.** The first line contains an integer $T$, representing the number of testdata groups. Then follow $T$ groups of data. Each group has only two lines, with one integer per line. The integer in the first line is $x$. The integer in the second line is $k$.

**This problem uses special judge.** For each group of data, output one line with one integer, representing the $y$ you give. If there are multiple valid $y$, you may output any one of them. But you must satisfy the following three constraints: - $y$ is a positive integer. - $y$ has no leading $0$. - The length of $y$ does not exceed the length of $x$. In particular, if such a $y$ does not exist, output one line with $\texttt{-1}$.

### Constraints For all test points, it is guaranteed that $0 \leq x < 10^{(10^4)}$, $1 \leq T \leq 5000$, $1 \leq k \leq 1+\log_{10}\max(1,x)$. The input $x$ has no leading $0$. ### Notes The input $x$ may be very large. If $x < 10^t$, then the **length** of the input $x$ will not exceed $t$. The meaning of the formula $k \leq 1 + \log_{10}\max(1,x)$ in the constraints is that $k$ will not exceed the length of $x$. Translated by ChatGPT 5