Minimization by Swaps

Masha는 큰 수를 공부하고 있다. 그녀는 카드 $n$장을 한 줄로 늘어놓았다. 각 카드에는 $1$부터 $9$까지의 숫자가 하나씩 적혀 있다. 이 카드들이 모여 $n$자리 정수 $s$를 이룬다.

한 번의 연산에서 Masha는 인접한 카드 두 장을 골라 자리를 바꿀 수 있다. 카드를 뒤집어서 숫자를 다른 숫자로 바꿀 수는 없다. Masha가 수행할 수 있는 연산은 최대 $k$번이다. 결과로 얻을 수 있는 $n$자리 수 중 가장 작은 수는 무엇인가?

입력

첫 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 100\,000$). 이어지는 줄마다 테스트 케이스가 주어진다.

각 테스트 케이스는 공백으로 구분된 두 정수 $s$와 $k$가 한 줄에 주어진다. 정수 $s$는 양의 정수이며 $1$부터 $9$까지의 숫자로 이루어진다. 또한 $0 \le k \le 10^{18}$이다.

모든 수 $s$의 자릿수 합은 $100\,000$을 넘지 않는다.

출력

각 테스트 케이스에 대해, $s$의 인접한 두 자리를 최대 $k$번 바꾸어 얻을 수 있는 가장 작은 $n$자리 수를 한 줄에 출력한다.