Corrupted Password - Repovive Starter Round 5 | Repovive

17D. Corrupted Password

2000 pts1s256 MB

You are given two strings $a$ and $b$ of length $n$ consisting of lowercase English letters.

The strings are considered circular, meaning the character immediately following $a_n$ is $a_1$ .

In a single operation, you can choose an index $i$ ( $1 \le i \le n$ ) and perform the following changes simultaneously:

Change $a_i$ to the next letter in the alphabet (e.g., 'a' $\rightarrow$ 'b', 'y' $\rightarrow$ 'z', 'z' $\rightarrow$ 'a').
Change the character immediately to its right (i.e., $a_{i+1}$ if $i < n$ , or $a_1$ if $i = n$ ) to the previous letter in the alphabet (e.g., 'b' $\rightarrow$ 'a', 'z' $\rightarrow$ 'y', 'a' $\rightarrow$ 'z').

Find the minimum number of operations required to transform string $a$ into string $b$ . If it is impossible to do so, output -1.

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

The first line of each test case contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — the length of the strings.

The second line of each test case contains the string $a$ of length $n$ .

The third line of each test case contains the string $b$ of length $n$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

For each test case, output a single integer — the minimum number of operations required to transform $a$ into $b$ , or $-1$ if it is impossible.

Input

Case 1

3
abc
bca

Case 2

3
aaa
aba

Case 3

3
xyz
tba

Explanation

Case 1

For $a =$ "abc" and $b =$ "bca", Fady can match the password in $3$ operations:

Choose index 1: $a_1$ ('a') moves forward to 'b', and $a_2$ ('b') moves backward to 'a'. The string $a$ becomes "bac".
Choose index 2: $a_2$ ('a') moves forward to 'b', and $a_3$ ('c') moves backward to 'b'. The string $a$ becomes "bbb".
Choose index 2 again: $a_2$ ('b') moves forward to 'c', and $a_3$ ('b') moves backward to 'a'. The string $a$ becomes "bca", matching $b$ .

Case 2

No sequence of operations can transform "aaa" into "aba", so the answer is -1.

Output

Case 1

Case 2

-1

Case 3

You are given two strings $a$ and $b$ of length $n$ consisting of lowercase English letters.

The strings are considered circular, meaning the character immediately following $a_n$ is $a_1$ .

In a single operation, you can choose an index $i$ ( $1 \le i \le n$ ) and perform the following changes simultaneously:

Change $a_i$ to the next letter in the alphabet (e.g., 'a' $\rightarrow$ 'b', 'y' $\rightarrow$ 'z', 'z' $\rightarrow$ 'a').
Change the character immediately to its right (i.e., $a_{i+1}$ if $i < n$ , or $a_1$ if $i = n$ ) to the previous letter in the alphabet (e.g., 'b' $\rightarrow$ 'a', 'z' $\rightarrow$ 'y', 'a' $\rightarrow$ 'z').