Rearrange String K Distance Apart

You are given a string S and an integer K. Your task is to rearrange the characters of S such that the same characters are at least K distance apart. If there are multiple valid rearrangements, you must return the lexicographically smallest one. If no rearrangement is possible, output impossible.

Formally, for the rearranged string R of length n, for any two identical characters R[i] = R[j] with i < j, it must hold that:

$$j - i \ge K$$

If K = 1, then any rearrangement is valid. In this case, the lexicographically smallest rearrangement is simply the sorted order of the string.

Note: The lexicographical order is determined by the ASCII values of characters.

inputFormat

The first line contains an integer T representing the number of test cases.

For each test case, two lines are provided:

• The first line is a non-empty string S consisting of lowercase letters.
• The second line is an integer K.

outputFormat

For each test case, print a single line containing the lexicographically smallest rearranged string that satisfies the condition. If no valid rearrangement exists, print impossible.

## sample

5
aabb
2
aaab
2
abcde
1
aabbcc
3
aabbccdd
2

abab
impossible
abcde
abcabc
abcdabcd

</p>