#include <bits/stdc++.h>
using namespace std;
int main() {
    string s, p;
    cin >> s >> p;
    string combined = p + "$" + s;
    int n = combined.size();
    int m = p.size();
    vector<int> sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = combined[i]; }
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int a, int b) {
            if (rank[a] != rank[b]) return rank[a] < rank[b];
            int ra = (a + k < n) ? rank[a + k] : -1;
            int rb = (b + k < n) ? rank[b + k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
        rank = tmp;
    }
    vector<int> lcp(n, 0);
    vector<int> inv(n);
    for (int i = 0; i < n; i++) inv[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (inv[i] == n - 1) { k = 0; continue; }
        int j = sa[inv[i] + 1];
        while (i + k < n && j + k < n && combined[i + k] == combined[j + k]) k++;
        lcp[inv[i]] = k;
        if (k > 0) k--;
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // Tìm vị trí l..r trong combined = p$ + s
        // l, r là vị trí trong s, cần dịch sang combined
        // Hậu tố trong combined bắt đầu tại vị trí l trong s = m + 1 + l
        int pos_left = m + 1 + l;
        int pos_right = m + 1 + r;
        int inv_l = inv[pos_left];
        int inv_r = inv[pos_right];
        // LCP giữa hai hậu tố trong sa
        // LCP[inv_l] = LCP(sa[inv_l], sa[inv_l + 1])
        // Trả về min LCP trên đường đi giữa inv_l và inv_r (RMQ)
        if (inv_l > inv_r) swap(inv_l, inv_r);
        if (inv_l == inv_r) {
            cout << n - sa[inv_l] << endl;
        } else {
            int ans = INT_MAX;
            for (int x = inv_l; x < inv_r; x++) ans = min(ans, lcp[x]);
            cout << ans << endl;
        }
    }
    return 0;
}