Minimum Transformations on Strings

Given two strings ( A ) and ( B ) of length ( N ), determine the minimum number of transformations needed to convert ( A ) into ( B ) under the following operation: choose an integer ( i ) such that ( 1 \leq i < N ), and if ( sorted(A[0:i]) = sorted(B[N-i:N]) ) and ( sorted(A[i:N]) = sorted(B[0:N-i]) ), then the transformation is considered successful. If ( A = B ), no transformation is required (answer is 0). Otherwise, if there exists an index ( i ) satisfying the above condition, the answer is 2. If no such index exists, the answer is -1.

Note: The transformation operation is allowed at most once. The input consists of multiple test cases. For each test case, output the result on a new line.

inputFormat

The first line of the input contains an integer ( T ) indicating the number of test cases. Each test case is described by three lines. The first line of each test case contains an integer ( N ) (the length of the strings). The second line contains the string ( A ) and the third line contains the string ( B ).

outputFormat

For each test case, output a single line containing the minimum number of transformations required to turn ( A ) into ( B ). If no transformation is possible, output -1.## sample

2
5
abacd
cadab
4
abcd
badc

2
-1