Let's Permute The String

mimebdinfo 7th CPU CSE Programming C...
Limits 1s, 512 MB

Mr. Alex is one of the best programmer in your university. He is very interested in string. So, Mr. Alex asked you to solve a problem.

You are given two string of length nn as,

A = a1, a2, a3, …, an
B = b1, b2, b3, …, bn

You are allowed to do two types of shift, left shift or right shift. After left shift string “abc” converted to “bca” and in right shift “abc” converted to “cab.”

You are allowed to do only one shift in one operation.

You have to answer if it is possible to construct the second string BB from AA, after shifting the character from AA zero or more times. If possible then print the minimum number of operation need to construct BB from AA.

Input

The first line of the input contains a single integer tt (1t101 \le t \le 10) - the number of test cases. The descriptions of the sets follows.

The first line of each test case is an integer nn (1n20001 \le n \le 2000) - the length of the string.

Next two lines contain two strings AA and BB of length nn consist of lower case letters.

It is guaranteed that the sum of string lengths over all test cases does not exceed 20,000.

Output

For each test case print one integer - the minimum number of steps need to construct the string BB, otherwise print -1.

Sample

InputOutput
2
4
abcd
bcda
2
ab
aa
1
-1

After doing left shift 1 times: “abcd” → “bcda”.

And for right shift 3 times: “abcd” → “dabc” → “cdab” → “bcda”.

So the answer for this case is 1, not 3.


Submit

Login to submit.

Statistics

65% Solution Ratio
sajjad_99Earliest, 1M ago
Yasir_ArafatFastest, 0.0s
Yasir_ArafatLightest, 5.7 MB
md_jakariyaShortest, 385B
Toph uses cookies. By continuing you agree to our Cookie Policy.