infO(1)Cup 2025 Day 1 - Mirror | Nines

You are given an integer $N \gt 0$ and a number $K$. We first define, for any natural number $x$, the number

We then define the value of an integer $x$, denoted by $\text{value}_K(x)$, by:

Task

Given $N$ and $K$, what is the maximum value of any integer less than $N$? In other words, what is

Input data

The first line in the input data contains the number of test cases $T$. The $2T$ lines that follow contain the test cases we are interested in. The first line of a test case contains $D$, the number of digits of $N$, and $K$. The second line of a test case contains the integer $N$.

Output data

Output $T$ lines, the answers for the $T$ values of $N$ and $K$ you are given.

Constraints and clarifications

• Let $\sum D$ be the sum of $D$ for all test cases in a file.
• $1 \leq T \leq 100 \ 000$;
• $1 \leq \sum D \leq 1 \ 000 \ 000$;
• $-1 \leq K \leq D$.

Example

stdin

2
3 0
100
18 0
998877665544332211

stdout

199
1097999999999999999

Explanation

For the first test case, the optimum is given by $\text{value}_0(99) = 199$.
For the second test case, the optimum is given by $\text{value}_0(997 \ 999 \ 999 \ 999 \ 999 \ 999) = 1 \ 097 \ 999 \ 999 \ 999 \ 999 \ 999$.