I. Largest Divisible by Nine
time limit per test
1 second
memory limit per test
512 MB
input
standard input
output
standard output

Shaban loves divisibility by 9, he has a number x with $$$n$$$ digits and he wants to transform it to the maximum number that is divisible by 9 by performing exactly $$$k$$$ of the following operation:

Each operation consists of choosing any single digit of x and doing one of the following:

  • Increase the digit by 1, if its value is less than 9.
  • Decrease the digit by 1, if its value is greater than 0.

Shaban will do exactly $$$k$$$ operations to transform the initial number into a new $$$n$$$-digit number that satisfies two conditions:

  1. The new number must be divisible by 9.
  2. The new number must be the largest possible.

The resulting number can have leading zeros. If it's impossible to create such a number, you should print -1.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$), The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^7$$$), representing the number of digits in the number and the number of operations, respectively.

The second line of each test case contains a string of $$$n$$$ digits, representing the initial number. The string can have leading zeros.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single line containing the resulting $$$n$$$-digit number that is as large as possible and divisible by 9. If no such number can be formed within $$$k$$$ operations, print -1.

Example
Input
7
2 4
70
1 2
3
2 3
30
2 2
18
10 16
1234567890
11 5
31599146004
10 100
1356849840
Output
90
-1
00
27
9234567810
71599146003
9999999999
Note

First Test Case:

  • Start with the number 70.
  • Add 1 to the first digit: $$$70 \to 80$$$
  • Add 1 to the first digit again: $$$80 \to 90$$$
  • Add 1 to the second digit: $$$90 \to 91$$$
  • Subtract 1 from the second digit: $$$91 \to 90$$$

The maximum number you can obtain is $$$90$$$, and it is divisible by 9.

Second Test Case:

No matter how you change the digits, the number will never become divisible by 9. so the answer is $$$-1$$$.

Third Test Case:

  • Start with the number 30.
  • Subtract 1 from the first digit three times: $$$30 \to 20 \to 10 \to 00$$$
  • The resulting number is $$$00$$$, which is divisible by 9.

Fourth Test Case:

  • Start with the number 18.
  • Subtract 1 from the second digit one time: $$$18 \to 17$$$
  • add 1 to the first digit one time: $$$17 \to 27$$$
  • The resulting number is $$$27$$$, which is divisible by 9 and is the largest number you can have.