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.

Input

The first line of the input contains a single integer t (1≤ t ≤ 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≤ n ≤ 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.

Output

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.

Example

Input


6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc


Output


0
1
1
2
1
-1

Note

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.
/**
 * author: derrick20
 * created: 12/31/20 4:08 PM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class RotatingSubstrings {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int T = sc.nextInt();
        cases: while (T-->0) {
            int N = sc.nextInt();
            char[] s = "_".concat(sc.next()).toCharArray();
            char[] t = "_".concat(sc.next()).toCharArray();
            int[][] suffixS = new int[26][N + 2];
            int[][] suffixT = new int[26][N + 2];
            boolean anagram = true;
            for (int c = 0; c < 26; c++) {
                for (int i = N; i >= 1; i--) {
                    suffixS[c][i] = suffixS[c][i + 1] + (s[i] - 'a' == c ? 1 : 0);
                    suffixT[c][i] = suffixT[c][i + 1] + (t[i] - 'a' == c ? 1 : 0);
                }
                anagram &= suffixS[c][1] == suffixT[c][1];
            }
            if (!anagram) {
                out.println(-1);
                continue cases;
            }
            int[][] dp = new int[N + 1][N + 1];
            int oo = (int) 1e4;
            for (int r1 = 0; r1 <= N; r1++) {
                for (int r2 = r1; r2 <= N; r2++) {
                    if (r1 == 0 && r2 == 0) continue;
                    dp[r1][r2] = oo;
                    if (r1 >= 1 && r2 >= 1 && s[r1] == t[r2]) {
                        // freebie match
                        dp[r1][r2] = min(dp[r1][r2], dp[r1 - 1][r2 - 1]);
                    }
                    if (r1 >= 1) {
                        // Pick up the char in s
                        dp[r1][r2] = min(dp[r1][r2], dp[r1 - 1][r2] + 1);
                    }
                    if (r2 >= 1) {
                        int c = t[r2] - 'a';
                        int bagAmt = suffixS[c][r1 + 1] - suffixT[c][r2 + 1];
                        if (bagAmt > 0) {
                            // Pick up a char from our bag
                            dp[r1][r2] = min(dp[r1][r2], dp[r1][r2 - 1]);
                        }
                    }
                }
            }
            out.println(dp[N][N]);
        }
        out.close();
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
    
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
    
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
    
        char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }
    
        int nextInt() {
            return (int) nextLong();
        }
    
        long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }
    
        double nextDouble() {
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            double cur = nextLong();
            if (c != '.') {
                return neg ? -cur : cur;
            } else {
                double frac = nextLong() / cnt;
                return neg ? -cur - frac : cur + frac;
            }
        }
    
        String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}