Unique Derangements

You are given a string (s) and an integer (n). Your task is to generate (n) unique derangements of (s). A derangement is a permutation of the characters of (s) such that for every index (i), the character at that index is different from the original character in (s). In other words, for a derangement (p) of (s), it must hold that (p[i] \neq s[i]) for all valid indices (i).

The number of derangements of a set of size (m) is given by the formula:
[ !m = m! \sum_{i=0}^{m} \frac{(-1)^i}{i!} ]

If it is impossible to produce (n) derangements (for example, when (s) has length 1), you should output only the available ones (which may be empty).

inputFormat

The input begins with an integer (t) ((1 \le t \le 10)) on a single line representing the number of test cases. Each of the following (t) lines contains a test case in which a string (s) and an integer (n) (separated by spaces) are given. The string (s) consists of distinct characters.

outputFormat

For each test case, output each valid derangement on a new line in the order they are found. All results for all test cases are printed sequentially. There is no extra separator between test cases.## sample

1
abc 2

bca
cab