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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;



public class COVID {

	static int[] fac;
	static int mod=998244353;
	static Scanner sc;
	static PrintWriter pw;
	static ArrayList<Integer>[] adjList;
	static boolean[]vis;

	
public static void main(String[] args) throws Exception {
		sc = new Scanner(System.in);
		pw =new PrintWriter(System.out);
		int tc=sc.nextInt();
		h:while(tc-->0) {
			int n=sc.nextInt();
			char[] s=sc.next().toCharArray();
			char[] t=sc.next().toCharArray();
			int[] cnt=new int[26];
			int[][] scnt=new int[26][n];
			int[][] tcnt=new int[26][n];
			for(int i=0;i<n;i++)
			{
				cnt[s[i]-'a']++;
				cnt[t[i]-'a']--;
				scnt[s[i]-'a'][i]++;
				tcnt[t[i]-'a'][i]++;
			
			}
			for(char c=0;c<26;c++)
			for(int i=n-2;i>=0;i--) {
				scnt[c][i]+=scnt[c][i+1];
				tcnt[c][i]+=tcnt[c][i+1];
			}
			for(int a:cnt)
				if(a!=0)
				{
					pw.println(-1);
					continue h;
				}
			int [] dp=new int[n+1];
			for(int i=1;i<=n;i++) {
				int tmp=0;
				for(int j=1;j<=n;j++) {
					int y=dp[j];
					boolean ok=true;
					for(int c=0;c<26;c++) {
						if(scnt[c][i-1]<tcnt[c][j-1])
							ok=false;
					}
					if(s[i-1]==t[j-1]&&ok)
						dp[j]=tmp+1;
					else if(dp[j-1]>dp[j])
						dp[j]=dp[j-1];
					tmp=y;
				}
	//			System.out.println(Arrays.toString(dp));
			}
	//		System.out.println(dp[n]);
			pw.println(n-dp[n]);
		}		
		
		pw.flush();
		pw.close();
	}



	static long gcd(long a, long b) {
		return (b==0)?a:gcd(b,a%b);
	}
	static long lcm(long a, long b) {
		return a/gcd(a,b)*b;
	}
	public static int log(int n , int base) {
		int ans=0;
		while(n+1>base) {
			ans++;
			n/=base;
		}
		return ans;
	}
	static long square(long l) {
		return l*l;
	}
	static int pow(int b,long e) {
		int ans=1;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b));
			e>>=1;
		b=(int)((b*1l*b));
		}
		return ans;
	}
	static int powmod(int b,long e, int mod) {
		int ans=1;
		b%=mod;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b)%mod);
			e>>=1;
			b=(int)((b*1l*b)%mod);
		}
		return ans;
	}




static public class FenwickTree {
int[] ft;int n;

public FenwickTree(int n)  {
	this.n=n;
	ft= new int[n+1];
}

public int LSONE(int i) {
	return i&(-i);
}

public void update_point(int  k ,int val) {//O(log n) because K will at worst case incremented with the number of ones in n so if to get number of bit
	// it's log(n)
	k=n-k;
	while(k<=n) {
		ft[k]+=val;
		k+=LSONE(k);
	}
}

public int query(int k) {
	// we keep adding ft[k]+ft[k']+ft[k"]+... where k' =k-LSONE(K) till k==0 it's also O(log(n))
	k=n-k;
	int sum =0;
	while(k>0) {
		sum+=ft[k];
		k-=LSONE(k);
	}
	return sum;
}





}


	static class Pair implements Comparable<Pair>{
		int  x;int y;

		public Pair(int a,int b) {
			this.x=a;y=b;
		}



		public int compareTo(Pair o) {
			return (x==o.x)?((y>o.y)?1:(y==o.y)?0:-1):((x>o.x)?1:-1);
		}


		@Override

		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}





	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr=new long[n];
			for(int i=0;i<n;i++)
				arr[i]=nextLong();
			return arr;
		}
		public int[] nextIntArr(int n) throws IOException {
			int[] arr=new int[n];
			for(int i=0;i<n;i++)
				arr[i]=nextInt();
			return arr;
		}
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine()," ,");
			return st.nextToken();
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}


		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}