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.

Copy String

Examples