Background

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.

Problem Description

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.

Input Format

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$.

Output Format

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}$.

5
1
1
14
1
514
2
1234
1
123456
6

9
8
516
7
877777

Hint

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