Given two strings $s$ and $t$ of length $n$, you aim to transform $s$ into $t$ through a series of the following operations:

• Construct a new string $s'$ of length $n$,where $s'_1=s_1$. For each $1 \lt i \le n$, $s'_i$ can be either $s_i$ or $s_{i-1}$. Then replace $s$ with $s'$.

Your task is to achieve this transformation using the minimum number of operations. You also need to output the solution by printing the constructed string $s'$ after each operation. If the transformation cannot be achieved in less than or equal to $k_{\mathrm{max}}$ operations, output -1.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$, $k_{\mathrm{max}}$ ($1 \le n \cdot k_{\mathrm{max}} \le 10^6$) — the length of two strings and the maximum number of operations that can be used.

The second line of each test case contains one string $s$ of length $n$.

The third line of each test case contains one string $t$ of length $n$.

It is guaranteed that the sum of $nk_{\mathrm{max}}$ over all test cases does not exceed $10^6$.

It is guaranteed that both $s$ and $t$ consist of lowercase Latin letters.

Output

For each test case:

• If you cannot achieve the transformation in less than or equal to $k_{\mathrm{max}}$ operations, simply output -1 in one line.
• Otherwise, on the first line, output one integer $k \le k_{\mathrm{max}}$ — the minimum number of operations. Then $k$ lines follow, each line contains one string of length $n$ — the string after each operation.

If there are multiple solutions, output any.

Note

In the first test case, obviously $s$ can be transformed to $t$ in one operation.

In the second test case, initially $s=t$, so no operation is needed.

In the fourth test case, although $s$ can be transformed to $t$ in two operations, but $k_{\mathrm{max}}=1$, so the answer is -1.