CF1363F Rotating Substrings

You are given two strings $ s $ and $ t $ , each of length $ n $ and consisting of lowercase Latin alphabets. You want to make $ s $ equal to $ t $ . You can perform the following operation on $ s $ any number of times to achieve it — - Choose any substring of $ s $ and rotate it clockwise once, that is, if the selected substring is $ s[l,l+1...r] $ , then it becomes $ s[r,l,l + 1 ... r - 1] $ . All the remaining characters of $ s $ stay in their position. For example, on rotating the substring $ [2,4] $ , string "abcde" becomes "adbce". A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. Find the minimum number of operations required to convert $ s $ to $ t $ , or determine that it's impossible.

The first line of the input contains a single integer $ t $ $ (1\leq t \leq 2000) $ — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ $ (1\leq n \leq 2000) $ — the length of the strings. The second and the third lines contain strings $ s $ and $ t $ respectively. The sum of $ n $ over all the test cases does not exceed $ 2000 $ .

For each test case, output the minimum number of operations to convert $ s $ to $ t $ . If it is not possible to convert $ s $ to $ t $ , output $ -1 $ instead.

For the $ 1 $ -st test case, since $ s $ and $ t $ are equal, you don't need to apply any operation. For the $ 2 $ -nd test case, you only need to apply one operation on the entire string ab to convert it to ba. For the $ 3 $ -rd test case, you only need to apply one operation on the entire string abc to convert it to cab. For the $ 4 $ -th test case, you need to apply the operation twice: first on the entire string abc to convert it to cab and then on the substring of length $ 2 $ beginning at the second character to convert it to cba. For the $ 5 $ -th test case, you only need to apply one operation on the entire string abab to convert it to baba. For the $ 6 $ -th test case, it is not possible to convert string $ s $ to $ t $ .