Problem: Given the string S and m queries. The i-th query is given by the two strings xi and yi.

For each query, answer the longest substring of the string S, starting with xi and ending with yi.

For the string S, | S | represents the length of S. Also, the fact that the character string T is a substring of the character string S means that a certain integer i exists and Tj = Si + j is satisfied for 1 ≤ j ≤ | T |. Where Tj represents the jth character of T.

Constraints

* 1 ≤ | S | ≤ 2 x 105
* 1 ≤ m ≤ 105
* 1 ≤ | xi |, | yi |
* $ \ sum ^ m_ {i = 1} $ (| xi | + | yi |) ≤ 2 x 105
* S and xi, yi consist only of half-width lowercase letters.

Input

The input is given in the following format.


S
m
x1 y1
x2 y2
::
xm ym


* The character string S is given on the first line.
* The number of queries m is given in the second line.
* Of the m lines from the 3rd line, the i-th query string xi, yi is given on the i-th line, separated by spaces.

Output

Answer the maximum substring length in the following format.


len1
len2
::
lenm


Output the longest substring length leni that satisfies the condition for the i-th query on the i-th line of the m lines from the first line. If there is no such substring, output 0.

Examples

Input

abracadabra
5
ab a
a a
b c
ac ca
z z


Output

11
11
4
3
0


Input

howistheprogress
4
ist prog
s ss
how is
the progress


Output

9
12
5
11


Input

icpcsummertraining
9
mm m
icpc summer
train ing
summer mm
i c
i i
g g
train i
summer er


Output

2
10
8
0
4
16
1
6
6

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

class SuffixArray {
    const ll n;
    const string str;
    vector<ll> sa, lcp;
public:
    SuffixArray(const string& s) : str(s), n(s.size()) {}
    vector<ll> make_sa() {
        sa.assign(n+1, 0);
        rep(i, n+1) sa[i] = i;
        vector<ll> rank(all(str));
        rank.pb(-1);
        auto f = [&](ll idx, ll len) {
            return idx + len <= n ? rank[idx+len] : -1;
        };
        for (ll k = 1; k <= n; k <<= 1) {
            auto compare = [&](ll a, ll b) {
                if (rank[a] != rank[b]) return rank[a] < rank[b];
                else return f(a, k) < f(b, k);
            };
            sort(all(sa), compare);
            vector<ll> nrank(n+1, 0);
            rep(i, 1, n+1) {
                nrank[sa[i]] = nrank[sa[i-1]] + compare(sa[i-1], sa[i]);
            }
            rank = nrank;
        }
        return sa;
    }
    vector<ll> make_lcp() {
        assert(sa.size() > 0);
        lcp.assign(sa.size(), 0);
        vector<ll> rank(n+1);
        rep(i, n+1) rank[sa[i]] = i;
        ll h = 0;
        rep(i, n) {
            if (h > 0) --h;
            assert(rank[i] > 0);
            for (ll j = sa[rank[i]-1]; j + h < n && i + h < n; h++) {
                if (str[j+h] != str[i+h]) break;
            }
            lcp[rank[i]-1] = h;
        }
        return lcp;
    }
    P search(const string& s) {
        assert(lcp.size() > 0);
        ll l = -1, r = -1;
        {
            ll lb = 0, ub = n+1;
            while (ub - lb > 1) {
                ll mid = (lb + ub) / 2;
                if (str.substr(sa[mid], s.size()) >= s) {
                    ub = mid;
                }
                else {
                    lb = mid;
                }
            }
            l = ub;
        }
        {
            ll lb = 0, ub = n+1;
            while (ub - lb > 1) {
                ll mid = (lb + ub) / 2;
                if (str.substr(sa[mid], s.size()) > s) {
                    ub = mid;
                }
                else {
                    lb = mid;
                }
            }
            r = ub;
        }
        return P(l, r);
    }
};
class SegmentManager {
    ll len;
    set<P> s;
    ll length(const P& p) {
        return p.second - p.first;
    }
    set<P>::iterator erase(const set<P>::iterator it) {
        len -= length(*it);
        return s.erase(it);
    }
    void insert(const P& p) {
        len += length(p);
        s.insert(p);
    }
    set<P>::iterator lb(ll l) {
        return s.lower_bound({l, l});
    }
    set<P>::iterator ub(ll l) {
        return lb(l+1);
    }
public:
    SegmentManager() : len(0) {}
    void add(ll l, ll r) {
        if (r <= l) return;
        erase(l, r);
        // merge right
        {
            auto it = lb(r);
            if (it != s.end() && it->first == r) {
                r = it->second;
                erase(it);
            }
        }
        // merge left
        {
            auto it = lb(l);
            if (it != s.begin()) {
                --it;
                if (it->second == l) {
                    l = it->first;
                    erase(it);
                }
            }
        }
        // add
        insert({l, r});
    }
    void erase(ll l, ll r) {
        if (r <= l) return;
        // cut left
        {
            auto it = lb(l);
            if (it != s.begin()) {
                --it;
                if (it->second > l) {
                    insert({it->first, l});
                    if (it->second > r) {
                        insert({r, it->second});
                        erase(it);
                        return;
                    }
                    erase(it);
                }
            }
        }
        auto it = lb(l);
        auto itr = lb(r);
        while (it != itr) {
            if (it->second > r) {
                insert({r, it->second});
                it = erase(it);
                break;
            }
            it = erase(it);
        }
    }
    bool is_in(ll l, ll r) {
        assert(r >= l);
        auto it = ub(l);
        if (it == s.begin()) return false;
        --it;
        return it->first <= l && r <= it->second;
    }
    bool is_in(ll pos) { return is_in(pos, pos+1); }
    ll length() { return len; }
    ll count() { return s.size(); }
    void out() {
        each(p, s) {
            cout << "[" << p.first << ", " << p.second << ")" << endl;
        }
    }
};
// SegmentTree<int> seg(n, 0x7FFFFFFF, [](int a, int b){return min(a, b);});
template <class T>
class SegmentTree {
    using func_t = function<T(T, T)>;
    const int sz, n;
    const T id;
    func_t merge;
    vector<T> data;
    int expand(int n) const { return n == 1 ? n : expand((n + 1) / 2) * 2; }
public:
    SegmentTree(const vector<T> &init, T id, func_t merge) :
        sz(init.size()), n(expand(sz)), id(id), data(n * 2, id), merge(merge) {
        copy(begin(init), end(init), begin(data)+n);
        RREP(i, n) {
            data[i] = merge(data[i * 2 + 0], data[i * 2 + 1]);
        }
    }
    int size() const { return sz; }
    void update(int p, T val) {
        assert (0 <= p && p < sz);
        data[p += n] = val;
        while (p /= 2) data[p] = merge(data[p * 2], data[p * 2 + 1]);
    }
    T find(int l, int r) const {
        assert (0 <= l && l <= r && r <= sz);
        l += n; r += n;
        T res1 = id, res2 = id;
        while (l != r) {
            if (l % 2) res1 = merge(res1, data[l++]);
            if (r % 2) res2 = merge(data[--r], res2);
            l /= 2; r /= 2;
        }
        return merge(res1, res2);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S; cin >> S;
    SuffixArray Sa(S);
    vector<ll> sa = Sa.make_sa();
    vector<ll> lcp = Sa.make_lcp();
    SegmentTree<ll> rmq(sa, linf, [](ll a, ll b) { return min(a, b); });
    SegmentTree<ll> rMq(sa, -linf, [](ll a, ll b) { return max(a, b); });
    ll Q; cin >> Q;
    rep(q, Q) {
        string s1, s2; cin >> s1 >> s2;
        P p1 = Sa.search(s1);
        P p2 = Sa.search(s2);
        if (p1.second <= p1.first || p2.second <= p2.first) {
            cout << 0 << endl;
        }
        else {
            ll l = rmq.find(p1.first, p1.second);
            ll r = rMq.find(p2.first, p2.second);
            // cout << l << " " << r << endl;
            if (r < l) cout << 0 << endl;
            else {
                ll ans = r+s2.size()-l;
                if (ans < s1.size()) cout << 0 << endl;
                else cout << ans << endl;
            }
        }
    }
}