Lexicographically Smallest String Construction

You are given a string s and an integer k. In one move, you may choose any character from s and move it to the beginning of the string. Your task is to compute the lexicographically smallest string possible after performing exactly k moves.

The problem can be summarized as follows:

• If k = 0, no moves can be made and the string remains unchanged.
• If k > 1, you can achieve any permutation of s, so the lexicographically smallest string is the sorted string.
• If k = 1, only one move is allowed. In this case, by moving each character one by one to the beginning, you have to choose the best outcome among these moves.

Note: All formulas should be written in LaTeX format when needed. For example, the condition for k > 1 can be expressed as \( k > 1 \).

inputFormat

The first line of input contains a single integer \(T\) indicating the number of test cases. Each of the following \(T\) lines contains a string \(s\) and an integer \(k\) separated by space.

Constraints:

• The string \(s\) consists of lowercase English letters (it might be empty).
• The integer \(k\) is non-negative.

outputFormat

For each test case, output the lexicographically smallest string possible after exactly \(k\) moves. Each answer should be printed on a new line.

## sample

2
cba 1
dacb 2

acb
abcd

</p>