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;

struct RangeMinimumQuery
{
    using type = int;
    static type id() { return INT_MAX; }
    static type op(const type &l, const type &r) { return min(l, r); }
};

struct RangeMaximumQuery
{
    using type = int;
    static type id() { return -INT_MAX; }
    static type op(const type &l, const type &r) { return max(l, r); }
};

template <typename M>
struct SegmentTree
{
    int n;
    const int INF = 2147483647;
    std::vector<int> node;
    // v を基に初期化
    SegmentTree(const std::vector<int> &v)
    {
        // n は v.size() 以上の最小の2冪
        n = 1;
        while (n < int(v.size()))
            n *= 2;
        node.resize(2 * n - 1, M::id());

        // i の子 -> 2*i+1, 2*i+2 , 親 -> (i-1)/2
        for (int i = 0; i < int(v.size()); i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = M::op(node[2 * i + 1], node[2 * i + 2]);
    }
    // x 番目を val に更新
    void update(int x, int val)
    {
        x += n - 1;
        node[x] = val;
        while (x > 0)
        {
            x = (x - 1) / 2;
            node[x] = M::op(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    // [a, b) の op
    // k := 今居るノード
    int query(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        if (r <= a || b <= l)
            return M::id();
        if (a <= l && r <= b)
            return node[k];

        int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return M::op(vl, vr);
    }
};

class SuffixArray
{
    int n;
    std::string str;
    std::vector<int> sa, rank;

    template <typename Compare>
    int binarySearch(const string &t)
    {
        int m = t.size();
        int lb = -1, ub = n + 1;
        while (ub - lb > 1)
        {
            int mid = (ub + lb) / 2;
            if (Compare()(strncmp(str.c_str() + sa[mid], t.c_str(), m), 0))
            {
                lb = mid;
            }
            else
            {
                ub = mid;
            }
        }
        return ub;
    }

  public:
    // 構築 O(n (logn)^2)
    SuffixArray(const std::string _s) : n(_s.size()), str(_s), sa(n + 1), rank(n + 1)
    {
        for (int i = 0; i <= n; i++)
        {
            sa[i] = i;
            rank[i] = i < n ? str[i] : -1;
        }
        std::vector<int> tmp(n + 1);
        for (int k = 1; k <= n; k *= 2)
        {
            // (rank[i], rank[i+k]), (rank[j], rank[j+k]) を比較
            auto compare_sa = [=](int i, int j) {
                if (rank[i] != rank[j])
                    return rank[i] < rank[j];
                else
                {
                    int ri = i + k <= n ? rank[i + k] : -1;
                    int rj = j + k <= n ? rank[j + k] : -1;
                    return ri < rj;
                }
            };
            std::sort(sa.begin(), sa.end(), compare_sa);
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++)
            {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++)
            {
                rank[i] = tmp[i];
            }
        }
    }
    // O(|t|logn)
    bool contain(const std::string &t)
    {
        int lb = 0, ub = n;
        while (ub - lb > 1)
        {
            int mid = (lb + ub) / 2;
            if (str.compare(sa[mid], t.size(), t) < 0)
                lb = mid;
            else
                ub = mid;
        }
        return str.compare(sa[ub], t.size(), t) == 0;
    }
    // 高さ配列 := 接尾辞配列における隣接要素で先頭何文字が共通しているか
    // つまり, lcp[i] = str[sa[i]..] と str[sa[i+1]..] の先頭共通文字数
    // O(n)
    std::vector<int> getLcp()
    {
        for (int i = 0; i <= n; i++)
            rank[str[i]] = i;
        int h = 0;
        std::vector<int> lcp(n + 1);
        for (int i = 0; i < n; i++)
        {
            int j = sa[rank[i] - 1];
            if (h > 0)
                h--;
            for (; j + h < n && i + h < n; h++)
            {
                if (str[j + h] != str[i + h])
                    break;
            }
            lcp[rank[i] - 1] = h;
        }
        return lcp;
    }
    std::vector<int> getSa()
    {
        return sa;
    }
    int lowerBound(const string &t)
    {
        return binarySearch<std::less<int>>(t);
    }
    int upperBound(const string &t)
    {
        return binarySearch<std::less_equal<int>>(t);
    }
};

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    int m;
    cin >> S >> m;
    SuffixArray sArray(S);
    vector<int> sa = sArray.getSa();
    // printv(sa);
    SegmentTree<RangeMaximumQuery> maxTree(sa);
    SegmentTree<RangeMinimumQuery> minTree(sa);
    while (m--)
    {
        string x, y;
        cin >> x >> y;
        if (!sArray.contain(x) || !sArray.contain(y))
        {
            cout << 0 << endl;
            continue;
        }
        int xlb = sArray.lowerBound(x), xub = sArray.upperBound(x);
        // cout << xlb << " "<< xub << endl;
        int ylb = sArray.lowerBound(y), yub = sArray.upperBound(y);
        // cout << ylb << " "<< yub << endl;
        int st = minTree.query(xlb, xub), gt = maxTree.query(ylb, yub) + (int)y.size() - 1;
        if (st <= gt && st + (int)x.size() - 1 <= gt)
            cout << gt - st + 1 << endl;
        else
            cout << 0 << endl;
    }
}