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 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 from , after shifting the character from zero or more times. If possible then print the minimum number of operation need to construct from .
The first line of the input contains a single integer () - the number of test cases. The descriptions of the sets follows.
The first line of each test case is an integer () - the length of the string.
Next two lines contain two strings and of length consist of lower case letters.
It is guaranteed that the sum of string lengths over all test cases does not exceed 20,000.
For each test case print one integer - the minimum number of steps need to construct the string , otherwise print -1.
Input | Output |
---|---|
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. |