#include <bits/stdc++.h>
using namespace std;

class suffix_array {
public:
    suffix_array(std::string const& s_)
        : length(s_.length()),
          s(s_),
          sa(s.length()+1),
          rank(s.length()+1)
    {
        for(int i = 0; i <= length; ++i) {
            sa[i] = i;
            rank[i] = i < length ? s[i] : -1;
        }
        int k = 0;
        auto compare_sa = [this, &k](int i, int j) {
            if(rank[i] != rank[j]) {
                return rank[i] < rank[j];
            } else {
                int ri = i + k <= length ? rank[i + k] : -1;
                int rj = j + k <= length ? rank[j + k] : -1;
                return ri < rj;
            }
        };
        for(k = 1; k <= length; k *= 2) {
            sort(sa.begin(), sa.end(), compare_sa);

            std::vector<int> tmp(length+1);
            tmp[sa[0]] = 0;
            for(int i = 1; i <= length; ++i) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for(int i=0; i <= length; ++i) {
                rank[i] = tmp[i];
            }
        }
    }

    std::vector<int> get() const {
        return sa;
    }

    bool contain(std::string const& t) {
        int l = 0, r = length;
        while(r - l > 1) {
            int m = (l + r) / 2;
            if(s.compare(sa[m], t.length(), t) < 0) {
                l = m;
            } else {
                r = m;
            }
        }
        return s.compare(sa[r], t.length(), t) == 0;
    }

    int lower_bound(std::string const& t) {
        int l = 0, r = length + 1;
        while(r - l > 1) {
            int m = (l + r) / 2;
            if(s.compare(sa[m], std::string::npos, t) < 0) {
                l = m;
            } else {
                r = m;
            }
        }
        return r;
    }
    int upper_bound(std::string const& t) {
        int l = 0, r = length + 1;
        while(r - l > 1) {
            int m = (l + r) / 2;
            if(s.compare(sa[m], t.size(), t) <= 0) {
                l = m;
            } else {
                r = m;
            }
        }
        return r;
    }

private:
    int length;
    std::string s;
    std::vector<int> sa;
    std::vector<int> rank;
};


struct minimum {
    using type = int;
    static type id() {
        return std::numeric_limits<int>::max();
    }
    static type op(type const& l, type const& r) {
        return std::min(l, r);
    }
};

struct maximum {
    using type = int;
    static type id() {
        return 0;
    }
    static type op(type const& l, type const& r) {
        return std::max(l, r);
    }
};

template<typename Monoid>
class segment_tree {
    using T = typename Monoid::type;

public:
    segment_tree(std::vector<T> const& init)
        : sz(init.size()),
          n(expand(init.size()))
    {
        dat.assign(n*2, Monoid::id());
        std::copy(begin(init), end(init), begin(dat) + n);
        for(int i = n - 1; i >= 0; --i) {
            dat[i] = Monoid::op(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    segment_tree(int const n, T const& init = Monoid::id())
        : segment_tree(std::vector<T>(n, init))
    {}

    void update(int p, T val) {
        assert(0 <= p && p < sz);
        dat[p += n] = val;
        while(p /= 2) {
            dat[p] = Monoid::op(dat[p * 2], dat[p * 2 + 1]);
        }
    }

    // [l, r)
    T query(int l, int r) const {
        assert(0 <= l && l <= r && r <= sz);
        l += n;
        r += n;
        T res1 = Monoid::id(),
          res2 = Monoid::id();
        while(l != r) {
            if(l & 1) {
                res1 = Monoid::op(res1, dat[l++]);
            }
            if(r & 1) {
                res2 = Monoid::op(dat[--r], res2);
            }
            l /= 2;
            r /= 2;
        }
        return Monoid::op(res1, res2);
    }

    int size() const {
        return sz;
    }

private:
    int expand(int n) const {
        return n == 1 ? n : expand((n + 1) / 2) * 2;
    }

private:
    const int sz;
    const int n;
    std::vector<T> dat;
};

int main() {
    string s;
    cin >> s;
    const int n = s.length();
    suffix_array SA(s);
    auto sa = SA.get();
    segment_tree<minimum> seg1(n + 1);
    segment_tree<maximum> seg2(n + 1);
    for(int i = 0; i < n + 1; ++i) {
        seg1.update(i, sa[i]);
        seg2.update(i, sa[i]);
    }
    int m;
    cin >> m;
    for(int i=0; i<m; ++i) {
        string x, y;
        cin >> x >> y;
        int xl = SA.lower_bound(x),
            yl = SA.lower_bound(y);
        int xr = SA.upper_bound(x),
            yr = SA.upper_bound(y);
        int l = seg1.query(xl, xr);
        int r = seg2.query(yl, yr);

        int res = 0;
        if(xl < xr && yl < yr && l <= r && l + x.length() <= r + y.length()) {
            res = max(res, r + (int)y.size() - l);
        }
        cout << res << endl;
    }
}


Measured memory_bytes: 10692