Chip Stack Shuffle

There are two stacks of poker chips, S1 and S2. Each stack contains exactly C chips, and chips may have several colors. Every string lists chips from bottom to top.

One shuffle interleaves the two stacks to create a new stack S12 of length 2*C. The bottom chip of S12 is the bottom chip of S2, and the chip above it is the bottom chip of S1. Then the second chip from the bottom of S2 is placed, followed by the second chip from the bottom of S1, and so on until the top chip of S1 becomes the top chip of S12.

After a shuffle, the bottom C chips of S12 become the new S1, and the top C chips become the new S2. The same shuffle can then be repeated.

For each dataset, determine how many shuffles are needed to produce the target stack. The target is checked immediately after a shuffle creates S12.

The first line contains the number of datasets N. (1 <= N <= 1000)

Each dataset consists of four lines.

1. The number of chips in each stack, C (1 <= C <= 100)
2. A string of length C describing the initial stack S1 from bottom to top
3. A string of length C describing the initial stack S2 from bottom to top
4. A string of length 2*C describing the target stack from bottom to top

Each chip color is one uppercase letter from A through H, with no spaces or separators inside a string.

For each dataset, output one line containing the minimum number of shuffles required to create the target stack. If the target stack cannot be reached, output -1.