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.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author Andy Phan
 */
public class f {

    public static void main(String[] args) {
        FS in;
        PrintWriter out;
        
        try {
            in = new FS(new FileInputStream("substring.in"));
            out = new PrintWriter(new File("substring.out"));
        } catch(Exception e) {
            in = new FS(System.in);
            out = new PrintWriter(System.out);
        }
        int t = in.nextInt(); while(t-->0)
        new f().solve(in, out);
        
        out.close();
    }
    
    long MOD = 998244353;
    
    
    long pow(long a, long b) {
        long ret = 1;
        for(; b > 0; b >>= 1, a = (a*a)%MOD) if((b&1) == 1) ret = (ret*a)%MOD;
        return ret;
    }

    public void solve(FS in, PrintWriter out) {
        int n = in.nextInt();
        char[] a = in.next().toCharArray();
        char[] b = in.next().toCharArray();
        int[] count = new int[26];
        for(char c : a) count[c-'a']++;
        for(char c : b) count[c-'a']--;
        if(Arrays.stream(count).anyMatch(i->i!=0)) {
            out.println(-1);
            return;
        }
        int curr = 0;
        int tot = 0;
        int[][] sumA = new int[26][n+1];
        int[][] sumB = new int[26][n+1];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 26; j++) {
                sumA[j][i+1] = sumA[j][i];
                sumB[j][i+1] = sumB[j][i];
            }
            sumA[a[i]-'a'][i+1]++;
            sumB[b[i]-'a'][i+1]++;
        }
        int[][] dp = new int[n+1][n+1];
        dp[n][n] = 0;
        for(int i = n-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                dp[i][j] = Integer.MAX_VALUE/2;
                if(sumA[a[j]-'a'][j]-sumB[a[j]-'a'][i] < 0) dp[i][j] = Math.min(dp[i][j], dp[i][j+1]);
                if(b[i] == a[j]) dp[i][j] = Math.min(dp[i][j], dp[i+1][j+1]);
                dp[i][j] = Math.min(dp[i][j], dp[i+1][j]+1);
            }
        }
        out.println(dp[0][0]);
    }

    static class FS {

        BufferedReader in;
        StringTokenizer token;

        public FS(InputStream str) {
            in = new BufferedReader(new InputStreamReader(str));
        }

        public String next() {
            if (token == null || !token.hasMoreElements()) {
                try {
                    token = new StringTokenizer(in.readLine());
                } catch (IOException ex) {
                }
                return next();
            }
            return token.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}
