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>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

typedef long long LL;
typedef unsigned long long ULL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
inline double distance(double y1, double x1, double y2, double x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }

const int INF = 1L << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy = { 0, 1, 0, -1 }, dx = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）

using namespace std;


class SuffixArray {
    const int n;
    const string s;

public:
    vector<int> rank;
    vector<int> sa;

    SuffixArray(const string s): n(s.size()), s(s) {
        rank.resize(n + 1);
        sa.resize(n + 1);

        this->construct();
    }

    // sがpatternを含んでいるか
    bool contain(string pattern) {
        int l = 0, r = n;
        while (r - l > 1) {
            int c = (l + r) / 2;
            // Sのsa[c]文字目から|T|文字とTを比較
            if (s.compare(sa[c], pattern.length(), pattern) < 0) {
                l = c;
            }
            else {
                r = c;
            }
        }
        return s.compare(sa[r], pattern.length(), pattern) == 0;
    }

    int lowerBound(string pattern) {
        int a = -1, b = n;
        while (b - a > 1) {
            int c = (a + b) / 2;
            if (s.compare(sa[c], pattern.length(), pattern) < 0) {
                a = c;
            }
            else {
                b = c;
            }
        }
        if (s.compare(sa[b], pattern.length(), pattern) == 0) {
            return b;
        }
        return -1;
    }

    int upperBound(string pattern) {
        int a = -1, b = n + 1;
        while (b - a > 1) {
            int c = (a + b) / 2;
            if (s.compare(sa[c], pattern.length(), pattern) <= 0) {
                a = c;
            }
            else {
                b = c;
            }
        }
        return b;
    }

private:
    // (rank[i], rank[i + k])と(rank[j], rank[j + k])を比較
    struct compare {
        const SuffixArray& sa;
        int k;

        compare(const SuffixArray& sa, int k) : sa(sa) , k(k){}

        bool operator()( const int &i, const int &j) {
            if (sa.rank[i] != sa.rank[j]) {
                return sa.rank[i] < sa.rank[j];
            }
            else {
                int ri = i + k <= sa.n ? sa.rank[i + k] : -1;
                int rj = j + k <= sa.n ? sa.rank[j + k] : -1;
                return ri < rj;
            }
        }
    };

    // 文字列Sの接尾辞配列を構築
    void construct() {
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }

        vector<int> tmp(n + 1);
        for (int k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), compare(*this, k));
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare(*this, k)(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) {
                rank[i] = tmp[i];
            }
        }
    }
};

class SegmentTree {
public:
    unsigned int n = 1;
    vector<int> dat;

    SegmentTree(vector<int> v) {
        while (n < v.size()) { n *= 2; }   // sz以上の最小の2冪
        dat.resize(2 * n - 1, INT_MAX);

        // 最下段
        for (int i = 0; i < v.size(); ++i) {
            dat[i + n - 1] = v[i];  // 最下段はn - 1からはじまる
        }
        // 木の全体を更新
        for (int i = n - 2; i >= 0; --i) {
            dat[i] = min(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }

    // 元の配列でのidxをxにし、木を更新
    void update(int idx, int x) {
        idx += n - 1;   // 木での対象のインデックス
        dat[idx] = x;
        while (idx > 0) {
            idx = (idx - 1) / 2;                                  // 親のインデックス
            dat[idx] = min(dat[idx * 2 + 1], dat[idx * 2 + 2]);   // 左の子と右の子
        }
    }

    // 区間[a, b)の最小値
    int query(int a, int b) {
        return this->query(a, b, 0, 0, n);
    }

private:

    // [a, b)の最小値をノードk（区間[l, r]）から検索
    int query(int a, int b, int k, int l, int r) {
        assert(a < b && l < r);
        // 範囲外
        if (r <= a || b <= l) {
            return INT_MAX;
        }
        // 完全に含む
        if (a <= l && r <= b) {
            return this->dat[k];
        }
            // 一部含む
        else {
            int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);    // 左の子
            int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);    // 右の子
            return min(vl, vr);
        }
    }
};


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

    string S;
    cin >> S;
    string T(S);
    reverse(ALL(T));
    SuffixArray sa(S);
    SuffixArray sa_rev(T);
    SegmentTree st(sa.sa);
    SegmentTree st_rev(sa_rev.sa);

    int m;
    cin >> m;
    FOR(i, 0, m) {
        string x, y;
        cin >> x >> y;
        reverse(ALL(y));

        int low = sa.lowerBound(x);
        int up = sa.upperBound(x);
        if (low == -1) {
            print(0);
            continue;
        }


        int rev_low = sa_rev.lowerBound(y);
        int rev_up = sa_rev.upperBound(y);
        if (rev_low == -1) {
            print(0);
            continue;
        }

        long s = st.query(low, up);
        long t = S.size() - st_rev.query(rev_low, rev_up);
        if (s + x.length() <= t && s <= t - y.length()) {
            print(t - s);
        } else {
            print(0);
        }
    }

    return 0;
}