#include <bits/stdc++.h>

using namespace std;

bool intersect(const string &a, const string &b) 
{
    for (char c : a) 
    {
        if (b.find(c) != string::npos) 
        {
            return true;
        }
    }
    return false; 
}


void run() 
{
    int n, q; 
    cin >> n >> q;
    vector<string> s(n); 
    for (auto &x : s)
    {
        cin >> x;
    }

    map<string, set<int>> m; 
    for (int i = 0; i < n; i ++ ) 
    {
        m[s[i]].emplace(i);
    }

    while (q -- ) 
    {
        int x, y; 
        cin >> x >> y; 
        x --, y --;
        if (x > y) swap(x, y);
        if (intersect(s[x], s[y])) 
        {
            cout << y - x << '\n';
            continue;
        }

        int ans = 1e9;
        for (auto &[k, v] : m) 
        {
            if (k == s[x] || k == s[y])
            {
                continue;
            }

            auto it = v.lower_bound(x);
            if (it != v.end()) 
            {
                ans = min(ans, *it - x);
            }
            if (it != v.begin()) 
            {
                it --;
                ans = min(ans, y - *it);
            }
        }

        if (ans > y - x && ans != 1e9) 
        {
            ans = 2 * (ans - (y - x)) + y - x;
        }

        ans = max(ans, y - x);
        if (ans == 1e9) 
        {
            ans = -1;
        }

        cout << ans << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t -- )
    {
        run();
    }

    return 0;
}