Маша изучает большие числа. Она положила в ряд $$$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$$$ раз поменять местами две соседние цифры.
4321 09 121241127 10692 1
321 9 11122247 629