#include <bits/stdc++.h>
using namespace std;
long long dp[2001][2001];
int suf_s[2001][30], suf_t[2001][30];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= n; j++) dp[i][j] = LLONG_MAX;
    dp[n][n] = 0;
    for (int i = 0; i < 30; i++) {
      suf_t[n][i] = 0;
      suf_s[n][i] = 0;
    }
    for (int i = n - 1; i >= 0; i--)
      for (int j = 0; j < 30; j++) {
        suf_t[i][j] = suf_t[i + 1][j] + (t[i] - 'a' == j);
        suf_s[i][j] = suf_s[i + 1][j] + (s[i] - 'a' == j);
      }
    for (int i = n; i >= 0; i--)
      for (int j = n; j >= i; j--) {
        if (dp[i][j] != LLONG_MAX) {
          if (i != 0 && s[i - 1] == t[j - 1]) {
            dp[i - 1][j - 1] = min(dp[i - 1][j - 1], dp[i][j]);
          } else {
            if (j != 0 &&
                suf_s[i][t[j - 1] - 'a'] - suf_t[j][t[j - 1] - 'a'] > 0) {
              dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + 1);
            }
            if (i != 0) dp[i - 1][j] = min(dp[i - 1][j], dp[i][j]);
          }
        }
      }
    if (dp[0][0] == LLONG_MAX)
      cout << -1 << endl;
    else
      cout << dp[0][0] << endl;
  }
}
