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\leq t \leq 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\leq n \leq 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$.

Source: codeforces | Difficulty: MEDIUM


Solutions:
import os
os_input = os.read(0, int(10000000.0)).split()
os_input_pos = -1
answer_list = []

def read_s():
	global os_input_pos
	os_input_pos += 1
	return os_input[os_input_pos].decode()

def read_i():
	return int(read_s())

def write_s(v):
	answer_list.append(v)

def write_i(v):
	write_s(str(v))

def print_ans():
	os.write(1, '\n'.join(answer_list).encode())
	os.write(1, '\n'.encode())
T = read_i()
while T:
	T -= 1
	n = read_i()
	s = read_s()
	t = read_s()
	if sorted(s) != sorted(t):
		write_i(-1)
		continue
	s_count = [[0 for i in range(n + 1)] for j in range(26)]
	t_count = [[0 for i in range(n + 1)] for j in range(26)]
	for i in range(n):
		for j in range(26):
			s_count[j][i] = s_count[j][i - 1]
			t_count[j][i] = t_count[j][i - 1]
		s_count[ord(s[i]) - ord('a')][i] += 1
		t_count[ord(t[i]) - ord('a')][i] += 1
	dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
	for i in range(0, n):
		for j in range(i, n):
			dp[i][j] = dp[i - 1][j] + 1
			if s[i] == t[j]:
				dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
			c = ord(t[j]) - ord('a')
			if s_count[c][i] < t_count[c][j]:
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
	write_i(dp[n - 1][n - 1])
print_ans()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	inf = 10 ** 9
	for _ in range(II()):
		n = II()
		s = SI()
		t = SI()
		cnts = [[0] * 26 for _ in range(n + 1)]
		cntt = [[0] * 26 for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			cnts[i][ord(s[i]) - 97] += 1
			cntt[i][ord(t[i]) - 97] += 1
			for j in range(26):
				cnts[i][j] += cnts[i + 1][j]
				cntt[i][j] += cntt[i + 1][j]
		ng = False
		for j in range(26):
			if cnts[0][j] != cntt[0][j]:
				ng = True
				break
		if ng:
			print(-1)
			continue
		dp = [[inf] * (n + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(n + 1):
			for j in range(i, n + 1):
				if i == n and j == n:
					break
				pre = dp[i][j]
				if pre == inf:
					continue
				if i < j and i + 1 <= n:
					dp[i + 1][j] = min(dp[i + 1][j], pre + 1)
				if i + 1 <= n and j + 1 <= n and (s[i] == t[j]):
					dp[i + 1][j + 1] = min(dp[i + 1][j + 1], pre)
				if j + 1 <= n and cnts[i + 1][ord(t[j]) - 97] > cntt[j + 1][ord(t[j]) - 97]:
					dp[i][j + 1] = min(dp[i][j + 1], pre)
		print(dp[n][n])
main()


def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
	n = read_int()
	cnt = [0 for i in range(26)]
	ps = [[0 for j in range(n + 1)] for i in range(26)]
	pt = [[0 for j in range(n + 1)] for i in range(26)]
	s = input()
	t = input()
	for i in range(n):
		ch = ord(s[i]) - ord('a')
		cnt[ch] += 1
		for j in range(26):
			ps[j][i + 1] = ps[j][i] + (1 if ch == j else 0)
	for i in range(n):
		ch = ord(t[i]) - ord('a')
		cnt[ch] -= 1
		for j in range(26):
			pt[j][i + 1] = pt[j][i] + (1 if ch == j else 0)
	ok = True
	for i in cnt:
		if i != 0:
			ok = False
			break
	if not ok:
		print(-1)
	else:
		r = n
		while r >= 1 and s[r - 1] == t[r - 1]:
			r -= 1
		inf = int(100000000.0)
		dp = [[0 if i == 0 else inf for j in range(r + 1)] for i in range(r + 1)]
		for i in range(1, r + 1):
			for j in range(i, r + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
				ch = ord(t[j - 1]) - ord('a')
				if ps[ch][r] - ps[ch][i] > pt[ch][r] - pt[ch][j]:
					dp[i][j] = min(dp[i][j], dp[i][j - 1])
				dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
		print(dp[r][r])


def num(c):
	return ord(c) - 97
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input().strip()
	s2 = input().strip()
	char1 = [0] * 26
	char2 = [0] * 26
	for c in s1:
		char1[num(c)] += 1
	for c in s2:
		char2[num(c)] += 1
	if char1 != char2:
		print(-1)
		continue
	dp = [[(False, 0, 0) for j in range(n + 1)] for i in range(n + 1)]
	dp[0][0] = [True, 0, [0] * 26]

	def upd(a, b, val, sett):
		if not dp[a][b][0] or val > dp[a][b][1]:
			dp[a][b] = (True, val, sett)
	for i in range(n):
		for j in range(n):
			(valid, val, tab) = dp[i][j]
			if not valid:
				continue
			top = s1[i]
			bot = s2[j]
			if top == bot:
				if not dp[i + 1][j + 1][0] or val + 1 > dp[i + 1][j + 1][1]:
					dp[i + 1][j + 1] = [True, val + 1, tab]
			if tab[num(top)] > 0:
				sett = tab[:]
				sett[num(top)] -= 1
				if not dp[i + 1][j][0] or val > dp[i + 1][j][1]:
					dp[i + 1][j] = [True, val, sett]
			sett = tab[:]
			sett[num(bot)] += 1
			if not dp[i][j + 1][0] or val > dp[i][j + 1][1]:
				dp[i][j + 1] = [True, val, sett]
			del dp[i][j][2]
	poss = [dp[i][n][1] for i in range(n + 1)]
	print(n - max(poss))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	n = N()
	s = input()
	k = input()
	ssuf = [[] for i in range(n + 1)]
	ksuf = [[] for i in range(n + 1)]
	ssuf[-1] = [0] * 26
	ksuf[-1] = [0] * 26
	for i in range(n - 1, -1, -1):
		ssuf[i] = ssuf[i + 1].copy()
		ssuf[i][ord(s[i]) - 97] += 1
		ksuf[i] = ksuf[i + 1].copy()
		ksuf[i][ord(k[i]) - 97] += 1
	if ssuf[0] != ksuf[0]:
		print(-1)
		continue
	dp = [[inf] * (n + 1) for i in range(n + 1)]
	for j in range(n + 1):
		dp[0][j] = 0
	for i in range(1, n + 1):
		for j in range(i, n + 1):
			if s[i - 1] == k[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = dp[i - 1][j] + 1
				cur = ord(k[j - 1]) - 97
				if i < j and ssuf[i][cur] - ksuf[j][cur] > 0:
					dp[i][j] = min(dp[i][j], dp[i][j - 1])
	print(dp[n][n])


INF = float('inf')

def solve():
	N = int(input())
	A = input().strip()
	B = input().strip()
	Acount = [[0] * 26 for _ in range(N + 1)]
	Bcount = [[0] * 26 for _ in range(N + 1)]
	for i in range(N - 1, -1, -1):
		Acount[i][ord(A[i]) - ord('a')] += 1
		Bcount[i][ord(B[i]) - ord('a')] += 1
		for j in range(26):
			Acount[i][j] += Acount[i + 1][j]
			Bcount[i][j] += Bcount[i + 1][j]
	for i in range(26):
		if Acount[0][i] != Bcount[0][i]:
			return -1
	dp = [[INF] * (N + 1) for _ in range(N + 1)]
	for j in range(N + 1):
		dp[0][j] = 0
	for i in range(1, N + 1):
		s = ord(A[i - 1]) - ord('a')
		for j in range(i, N + 1):
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
			t = ord(B[j - 1]) - ord('a')
			if Acount[i][t] > Bcount[j][t]:
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
			if s == t:
				dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
	return dp[N][N]
T = int(input())
for _ in range(T):
	print(solve())