Maximum Unique Substring

You are given a string S and an integer K. Your task is to find a substring of length K with the highest number of unique characters. If there are multiple substrings with the same number of unique characters, you should output the lexicographically smallest one. If the string length is less than K, output an empty string.

Note: All comparisons are case-sensitive and the lexicographical order is determined by the standard character ordering.

Constraints:

• 1 ≤ T ≤ 10⁴ (number of test cases)
• 0 ≤ K ≤ |S|
• S consists of printable ASCII characters without spaces.

The solution should read input from stdin and output the results to stdout.

Mathematical Formulation:

Let \( S \) be a string and \( K \) be an integer. For each substring \( s = S[i:i+K] \) where \( 0 \leq i \leq |S|-K \), define \( u(s) \) as the number of unique characters in \( s \). The answer is the substring \( s^* \) such that \[ s^* = \min\{ s \mid u(s) = \max_{0 \leq i \leq |S|-K} u(S[i:i+K]) \}, \] where \(\min\) denotes the lexicographically smallest substring among those with the maximum unique character count.

inputFormat

The input is given via stdin and consists of multiple test cases. The first line contains an integer T, the number of test cases. For each test case, the following two lines are provided:

• The first line contains the string S.
• The second line contains the integer K.

outputFormat

For each test case, print on a separate line the substring of length K that contains the maximum number of unique characters. If multiple substrings satisfy this criterion, print the lexicographically smallest one. If S is shorter than K, print an empty line.

## sample

1
abcabc
3

abc

</p>