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.
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using vi = vector<long long>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<pair<long long, long long> >;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
const long long inf = 1001001001001001001;
const long long INF = 1001001001;
const long long mod = 1000000007;
const double eps = 1e-10;
template <class T>
bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
void out(T a) {
  cout << a << '\n';
}
template <class T>
void outp(T a) {
  cout << '(' << a.first << ',' << a.second << ')' << '\n';
}
template <class T>
void outvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++)
    cout << '(' << v[i].first << ',' << v[i].second << ')';
  cout << '\n';
}
template <class T>
void outvvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outvp(v[i]);
}
template <class T>
void outv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) {
    if (i) cout << ' ';
    cout << v[i];
  }
  cout << '\n';
}
template <class T>
void outvv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outv(v[i]);
}
template <class T>
bool isin(T x, T l, T r) {
  return (l) <= (x) && (x) <= (r);
}
template <class T>
void yesno(T b) {
  if (b)
    out("yes");
  else
    out("no");
}
template <class T>
void YesNo(T b) {
  if (b)
    out("Yes");
  else
    out("No");
}
template <class T>
void YESNO(T b) {
  if (b)
    out("YES");
  else
    out("NO");
}
template <class T>
void noyes(T b) {
  if (b)
    out("no");
  else
    out("yes");
}
template <class T>
void NoYes(T b) {
  if (b)
    out("No");
  else
    out("Yes");
}
template <class T>
void NOYES(T b) {
  if (b)
    out("NO");
  else
    out("YES");
}
void outs(long long a, long long b) {
  if (a >= inf - 100)
    out(b);
  else
    out(a);
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long modpow(long long a, long long b) {
  long long res = 1;
  a %= mod;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
vi seg;
long long N;
void init(vi v) {
  N = 1;
  while (N < v.size()) N *= 2;
  seg = vi(N * 2 - 1);
  for (long long i = 0; i < (long long)(v.size()); i++) seg[i + N - 1] = v[i];
  for (int i = N - 2; i >= 0; i--) seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
}
void add(long long i, long long x) {
  i = N + i - 1;
  seg[i] += x;
  while (i > 0) {
    i = (i - 1) / 2;
    seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
  }
}
long long getsum(long long a, long long b, long long k, long long l,
                 long long r) {
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return seg[k];
  long long c1 = getsum(a, b, k * 2 + 1, l, (l + r) / 2);
  long long c2 = getsum(a, b, k * 2 + 2, (l + r) / 2, r);
  return c1 + c2;
}
void chr(long long k, long long x) {
  long long s = getsum(0, k + 1, 0, 0, N);
  if (s <= x) return;
  add(k, x - s);
  add(k + 1, s - x);
}
int main() {
  long long t;
  cin >> t;
  for (long long tt = 0; tt < (long long)(t); tt++) {
    long long n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    vvi dp(n + 1, vi(n + 1));
    vvi c1(26, vi(n + 1)), c2(26, vi(n + 1));
    for (long long i = 0; i < (long long)(n); i++) {
      for (long long j = 0; j < (long long)(26); j++) {
        c1[j][i + 1] = c1[j][i];
        c2[j][i + 1] = c2[j][i];
      }
      c1[s[i] - 'a'][i + 1]++;
      c2[t[i] - 'a'][i + 1]++;
    }
    for (long long i = 0; i < (long long)(n); i++)
      for (long long j = 0; j < (long long)(n); j++) {
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
        bool ok = true;
        for (long long k = 0; k < (long long)(26); k++)
          if (c1[k][i] > c2[k][j]) ok = false;
        if (s[i] == t[j] && ok) chmax(dp[i + 1][j + 1], dp[i][j] + 1);
      }
    bool ok = true;
    for (long long i = 0; i < (long long)(26); i++)
      if (c1[i][n] - c2[i][n]) ok = false;
    if (ok)
      out(n - dp[n][n]);
    else
      out(-1);
  }
}
