Untitled

#include <bits/stdc++.h>

using namespace std;

#define ll long long

void FIO() {
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#else
    freopen("xmore.in", "r", stdin);
#endif
}


ll power(ll x, ll p, ll mod) {
    ll ret = 1;
    while (p) {
        if (p & 1) {
            ret = (ret * x) % mod;
        }
        p >>= 1;
        x = (x * x) % mod;
    }
    return ret;
}

int MaxN = 1e6 + 7;

struct stringHashing {
    vector<ll> pw1, pw2, invPw1, invPw2;
    int base1, base2, MOD1, MOD2;

    stringHashing() : pw1(MaxN), pw2(MaxN), invPw1(MaxN), invPw2(MaxN) {
        base1 = 131, base2 = 153, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
        pw1[0] = pw2[0] = 1;
        for (int i = 1; i < pw1.size(); ++i) {
            pw1[i] = (pw1[i - 1] * base1) % MOD1;
            pw2[i] = (pw2[i - 1] * base2) % MOD2;
        }
        invPw1[MaxN - 1] = power(pw1[MaxN - 1], MOD1 - 2, MOD1);
        invPw2[MaxN - 1] = power(pw2[MaxN - 1], MOD2 - 2, MOD2);
        for (int i = MaxN - 2; i >= 0; --i) {
            invPw1[i] = (invPw1[i + 1] * base1) % MOD1;
            invPw2[i] = (invPw2[i + 1] * base2) % MOD2;
        }
    }

    vector<pair<ll, ll>> hash(string &s) {
        vector<pair<ll, ll>> hs(s.size() + 1, {0, 0});
        for (int i = 0; i < s.size(); ++i) {
            hs[i + 1].first = (hs[i].first + (s[i] - '0' + 1) * pw1[i]) % MOD1;
            hs[i + 1].second = (hs[i].second + (s[i] - '0' + 1) * pw2[i]) % MOD2;
        }
        return hs;
    }

    pair<ll, ll> getRange(int l, int r, vector<pair<ll, ll>> &hs) {
        return {
                (hs[r + 1].first - hs[l].first + MOD1) * invPw1[l] % MOD1,
                (hs[r + 1].second - hs[l].second + MOD2) * invPw1[l] % MOD2
        };
    }
} H;


void solve() {
    int n;
    cin >> n;
    vector<string> v(n + 1);
    vector<vector<pair<ll, ll>>> hs(n + 1);
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        while (s.size() > 1 && s.back() == '0')
            s.pop_back();
        v[i] = s;
        hs[i] = H.hash(s);
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (v[x].size() != v[y].size()) {
            cout << (max(v[x].size(), v[y].size())) << '\n';
        } else {
            if (hs[x].back() == hs[y].back()) {
                cout << "-1\n";
                continue;
            }
            int l = 1, r = v[x].size(), ans = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (H.getRange(v[x].size() - mid, v[x].size() - 1, hs[x]) ==
                    H.getRange(v[y].size() - mid, v[y].size() - 1, hs[y])) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            cout << (v[x].size() - ans - 1) << '\n';
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    FIO();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}