#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int k;
const int sz = 15000;
vector<int> p;

void conv(string& s) {
    string t;
    t.resize(s.size());
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 35 || s[i] == 36) {
            t[i] = s[i] - 35;
        }
        if (s[i] >= 48 && s[i] <= 57) {
            t[i] = s[i] - 46;
        }
        if (s[i] >= 65 && s[i] <= 90) {
            t[i] = s[i] - 53;
        }
        if (s[i] >= 97 && s[i] <= 122) {
            t[i] = s[i] - 59;
        }
    }
    s.clear();
    int c;
    for (int i = t.size() - 1; i >= 0; i--) {
        c = t[i];
        for (int i = 0; i < 6; i++) {
            if (c%2 == 0) {
                s.push_back('0');
            } else {
                s.push_back('1');
            }
            c /= 2;
        }
    }
    reverse(s.begin(), s.end());
}

void pref_func(string& s) {
    p.resize(s.size());
    p[0] = 0;
    for (int i = 1; i < s.size(); i++) {
        p[i] = p[i - 1];
        while (p[i] > 0 && s[i] != s[p[i]]) {
            p[i] = p[p[i] - 1];
        }
        if (s[i] == s[p[i]]) {
            p[i]++;
        }
    }
}

void solve() {
    string x, y;
    cin >> x >> y;
    conv(x);
    conv(y);
    string s = x + '&' + y + y;
    pref_func(s);
    for (int i = p.size() - 1; i > x.size() + y.size(); i--) {
        if (p[i] == x.size()) {
            cout << x.size() - (i - x.size() - y.size()) << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}

int main() {
    int m;
    cin >> k >> m;
    while (m--) {
        solve();
    }
    return 0;
}