Минимизация обменами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

Маша изучает большие числа. Она положила в ряд $$$n$$$ карточек. На каждой карточке написана цифра от $$$1$$$ до $$$9$$$. Вместе они образуют $$$n$$$-значное целое число $$$s$$$.

За одну операцию Маша может взять две соседние карточки и поменять их местами (поворачивать карточки, превращая одни цифры в другие, нельзя). Маша может произвести не более $$$k$$$ операций. Какое минимальное $$$n$$$-значное число может получиться в итоге?

Входные данные

В первой строке задано целое число $$$t$$$ — число наборов входных данных ($$$1 \le t \le 100\,000$$$). Далее следуют сами наборы.

Каждый набор входных данных — это строка, в которой записаны через пробел целые числа $$$s$$$ и $$$k$$$. Число $$$s$$$ положительное и состоит из цифр от $$$1$$$ до $$$9$$$. Кроме того, $$$0 \le k \le 10^{18}$$$.

Суммарное число цифр во всех числах $$$s$$$ не превосходит $$$100\,000$$$.

Выходные данные

Для каждого набора входных данных выведите строку с ответом: минимальное $$$n$$$-значное число, которое может получиться из $$$s$$$, если не более $$$k$$$ раз поменять местами две соседние цифры.

Пример

Входные данные
4
321 0
9 1
21241127 10
692 1
Выходные данные
321
9
11122247
629