B. Magical Deletion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a magic string $$$s$$$ that consists of lowercase Latin letters and an integer $$$k$$$ $$$(k \lt |s|)$$$.

You can do the following operation exactly once:

  1. Choose a positive integer $$$a$$$ where $$$1 \leq a \leq |s|-k+1$$$.
  2. Let $$$s = \overline{c_1 c_2 \dots c_{|s|-1} c_{|s|}}$$$ where $$$c_i$$$ indicates the $$$i$$$-th character in $$$s$$$. Delete the substring $$$\overline{c_a c_{a+1} \dots c_{a+k-2} c_{a+k-1}}$$$ and then concatenate the remaining characters into a new string $$$x = \overline{c_1 c_2 \dots c_{a-2} c_{a-1} c_{a+k} c_{a+k+1} \dots c_{|s|-1} c_{|s|}}$$$ where the length of the string $$$x$$$ is $$$|s|-k$$$.

A magic string $$$y$$$ is said to be weaker that a magic string $$$z$$$ of the same length if at the leftmost position where the character inside $$$y$$$ and $$$z$$$ is different, the character inside $$$y$$$ appears earlier in the alphabet than the character inside $$$z$$$.

More formally, let $$$l$$$ be the leftmost position where the character inside $$$y$$$ and $$$z$$$ differs. Then, $$$y_l \lt z_l$$$. For example, the magic string $$$y =$$$ "codeforall" is weaker than the magic string $$$z =$$$ "codeforces" since the leftmost position where they differ is the $$$8$$$-th position and $$$y_8 =$$$ 'a' $$$ \lt $$$ 'c' $$$= z_8$$$.

Find the weakest possible string that you can achieve.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.

The only line for each test case contains a string $$$s$$$ consisting of lowercase Latin letters followed by an integer $$$k$$$ $$$(1 \leq k \lt |s| \leq 4 \cdot 10^5)$$$.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, output a string $$$x$$$ — the weakest magic string obtained after the operation.

Example
Input
5
haiti 2
ptlwqak 4
amogus 2
inthatpi 5
icodeforces 1
Output
hai
pak
agus
ini
codeforces
Note

For the first test case, we can delete the segment $$$[4,5]$$$ to get the string "hai". Other strings we can obtain by deleting other segments are "hti" and "iti". From all the possible strings obtained, the weakest one is "hai".

For the fifth test case, it can be proven that we can get the weakest magic string by deleting the segment $$$[1,1]$$$.