#pragma optimize ("Ofast");
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <string>
#include <unordered_map>
#include <cassert>
#include <bitset>

using namespace std;
//#define int long long
const int inf = 2e9;
const int mod = 998244353;

unsigned long long x[15001], y[15001], pw[15001];
unsigned long long xx[15001], yy[15001];
const unsigned long long p = 347;
int keys[256];
int zxc[64][6];
int n, i, j, g;

void solve() {
    vector <char> can;
    can.push_back('#');
    can.push_back('$');
    pw[0] = 1;
    for (i = 1; i <= 15000; i++) {
        pw[i] = pw[i - 1] * p;
    }
    for (i = 0; i < 10; i++) {
        can.push_back('0' + i);
    }
    for (i = 0; i < 26; i++) {
        can.push_back(i + 'A');
        can.push_back(i + 'a');
    }
    sort(can.begin(), can.end());
    for (i = 0; i < 64; i++) {
        keys[can[i]] = i;
    }
    for (i = 0; i < 64; i++) {
        for (j = 0; j < 6; j++) {
            if (i & (1 << j)) {
                zxc[i][5 - j] = 1;
            }
            else {
                zxc[i][5 - j] = 0;
            }
        }
    }
    int k, m;
    cin >> k >> m;
    n = k * 6;
    int last, idx;
    string s1, s2;
    int cx, cy;
    while (m--) {
        cin >> s1 >> s2;
        last = n - 1;
        for (i = 0; i < s1.size(); i++) {
            idx = keys[s1[i]];
            for (j = 0; j < 6; j++) {
                xx[last] = zxc[idx][j];
                last--;
            }
        }
        last = n - 1;
        for (i = 0; i < s2.size(); i++) {
            idx = keys[s2[i]];
            for (j = 0; j < 6; j++) {
                yy[last] = zxc[idx][j];
                last--;
            }
        }
        for (i = 0; i < n; i++) {
            x[i + 1] = x[i] * p + xx[i];
            y[i + 1] = y[i] * p + yy[i];
        }
        if (x[n] == y[n]) {
            cout << 0 << '\n';
            continue;
        }
        for (i = 1; i < n; i++) {
            if (x[n] == (y[n] - y[i] * pw[n - i]) * pw[i] + y[i]) {
                cout << i << '\n';
                break;
            }
        }
        if (i == n) {
            cout << -1 << '\n';
        }
    }
}

signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r ", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--) solve();
}
//Deisgned by skimono