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 optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MAX = 2e3 + 5;
const long long MAX2 = 11;
const long long MOD = 1e12;
const long long MOD2 = 1000005329;
const long long INF = 2e18;
const int dr[] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1, 0};
const double pi = acos(-1);
const double EPS = 1e-9;
const int block = 2000;
int tc, n, m, cnt[128], dp[MAX][MAX], pos[MAX];
string s, t;
bool st;
vector<int> v[128];
int f(int nw, int hit) {
  if (nw == -1) return 0;
  if (dp[nw][hit] != -1) return dp[nw][hit];
  if (s[nw] == t[nw + hit]) return dp[nw][hit] = f(nw - 1, hit);
  if (hit)
    return dp[nw][hit] = min(
               f(nw, hit - 1),
               f(nw - 1, hit + 1) + (v[s[nw]][pos[nw]] <= nw + hit ? 1 : MAX));
  return dp[nw][hit] =
             f(nw - 1, hit + 1) + (v[s[nw]][pos[nw]] <= nw + hit ? 1 : MAX);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> tc;
  for (int ntc = 1; ntc <= tc; ++ntc) {
    cin >> n >> s >> t;
    memset(cnt, 0, sizeof cnt);
    for (auto i : s) cnt[i]++;
    for (auto i : t) cnt[i]--;
    st = 1;
    for (int i = 0; i <= 127; ++i)
      if (cnt[i] != 0) st = 0;
    if (!st) {
      cout << "-1\n";
      continue;
    }
    --n;
    for (int i = 0; i <= 127; ++i) v[i].clear();
    for (int i = 0; i <= n; ++i) {
      pos[i] = cnt[s[i]]++;
      v[t[i]].push_back(i);
    }
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= n; ++j) dp[i][j] = -1;
    cout << f(n, 0) << '\n';
  }
  return 0;
}
