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:
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// O(n log n) で構築するやつ
// ・getIdx(i) := Suffix を辞書順に並べたときに i 番目に来るものは、元の文字列で何番目のインデックスからはじめた Suffix か？
// ・getLCP(i) := SuffixArray 上で i 番目と i+1 番目の要素の最長共通接頭辞はいくらか？
// ・is_greater: 辞書順 i 番目の Suffix がパターン文字列より大きいか見る
// ・is_less: 辞書順 i 番目の Suffix がパターン文字列より小さいか見る
// ・binary_search_greater: パターン文字列より大きい Suffix でインデックス最小のもの
// ・binary_search_less: パターン文字列より小さい Suffix でインデックス最小のもの
const int ALPH = 256;
struct SuffixArray {
private:
    string s;
    vector<int> rec, lcp, cnt;
    int len, cnt_size;
public:
    SuffixArray(string s_) : s(s_) {
        s += "$"; // 辞書順で最も小さいダミー文字
        len = s.length();
        cnt_size = max(ALPH, len); cnt.resize(cnt_size);
        rec = getArray();
        lcp = getLCPArray();
    }

    void dump_array(vector<int> &indices, vector<int> &classes) {
        fprintf(stderr, "# debug\n");
        fprintf(stderr, "# indices:");
        for(int i=0; i<len; i++) fprintf(stderr, " %d", indices[i]);
        fprintf(stderr, "\n");
        fprintf(stderr, "# classes:");
        for(int i=0; i<len; i++) fprintf(stderr, " %d", classes[i]);
        fprintf(stderr, "\n");
    }
    
    vector<int> getArray() {
        vector<int> indices(len), prev_idx(len);
        vector<int> classes(len), prev_cls(len);
        vector<int> tmp_val(len);

        // k == 0 はカウントソートのみ
        for(int i=0; i<len; i++) {
            cnt[ s[i] ]++;
        }
        for(int i=1; i<cnt_size; i++) {
            cnt[i] += cnt[i-1];
        }
        for(int i=len-1; i>=0; i--) {
            indices[ --cnt[ s[i] ] ] = i;
        }
        for(int i=1; i<len; i++) {
            int pena = (s[ indices[i] ] != s[ indices[i-1] ]);
            classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
        }
        
        for(int k=0; (1 << k) < len; k++) {
            swap(indices, prev_idx);
            swap(classes, prev_cls);
            for(int i=0; i<len; i++) {
                // 後半だけソート済みにしたものを indices に代入
                prev_idx[i] = prev_idx[i] - (1 << k);
                if(prev_idx[i] < 0) prev_idx[i] += len;
                tmp_val[i] = prev_cls[ prev_idx[i] ];
            }

            // 前半についてカウントソート
            fill(cnt.begin(), cnt.end(), (int)0);
            for(int i=0; i<len; i++) {
                cnt[ tmp_val[i] ]++;
            }
            for(int i=1; i<cnt_size; i++) {
                cnt[i] += cnt[i-1];
            }
            for(int i=len-1; i>=0; i--) {
                indices[ --cnt[ tmp_val[i] ] ] = prev_idx[i];
            }
            classes[ indices[0] ] = 0;
            for(int i=1; i<len; i++) {
                int shift = (1 << k);
                pair<int, int> pre(prev_cls[ indices[i-1] ], prev_cls[ (indices[i-1] + shift) % len ]);
                pair<int, int> cur(prev_cls[ indices[i  ] ], prev_cls[ (indices[i  ] + shift) % len ]);
                int pena = (pre != cur);
                classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
            }
        }
        return indices;
    }

    int size() {
        return rec.size();
    }
    // Suffix を辞書順に並べたときに idx 番目に来るものは、元の文字列で何番目のインデックスからはじめた Suffix か？
    int getIdx(int idx) {
        assert(0 <= idx and idx < size());
        return rec[idx];
    }
    // SuffixArray 上で idx 番目と idx+1 番目の要素の最長共通接頭辞はいくらか？
    int getLCP(int idx) {
        assert(0 <= idx and idx < size());
        return lcp[idx];
    }
    
    // 元の文字列の idx 番目以降の接尾辞は、パターン文字列 p に比べて大きいか？
    bool is_greater(string &p, int idx) {
        idx = getIdx(idx);
        int N = size(), M = p.size(), x, y;
        for(x=idx, y=0; x<N and y<M; x++, y++) {
            if(s[x] > p[y]) return true;
            if(s[x] < p[y]) return false;
        }
        return y >= M and x < N;
    }

    // 元の文字列の idx 番目以降の接尾辞は、パターン文字列 p に比べて小さいか？
    bool is_less(string &p, int idx) {
        idx = getIdx(idx);
        int N = size(), M = p.size(), x, y;
        for(x=idx, y=0; x<N and y<M; x++, y++) {
            if(s[x] < p[y]) return true;
            if(s[x] > p[y]) return false;
        }
        return x >= N and y < M;
    }
    
    // SA 配列上で、p より大きくなる要素であって最小のもの
    // そのような要素が存在しなければ -1
    int binary_search_greater(string &p) {
        int lb = -1, ub = len;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(is_greater(p, mid)) ub = mid;
            else lb = mid;
        }

        if(ub == len) return -1;
        return ub;
    }

    // SA 配列上で、p より小さくなる要素であって最大のもの
    // そのような要素が存在しなければ -1
    int binary_search_less(string &p) {
        int lb = -1, ub = len;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(is_less(p, mid)) lb = mid;
            else ub = mid;
        }
        if(lb == -1) return -1;
        return lb;
    }

    // LCP[i] := SA 配列上の i 番目と i+1 番目の最長共通接頭辞
    vector<int> getLCPArray() {
        vector<int> rank(len);
        for(int i=0; i<len; i++) {
            rank[ rec[i] ] = i;
        }

        vector<int> res(len, -1);
        int cons = 0;
        // 空文字列に関しては探索しない！
        for(int i=0; i+1<len; i++) {
            // i 文字目から始まる接尾辞に対して
            // SA 配列上で直前の要素をもってくる
            int pre = rec[ rank[i] - 1 ], cur = i;

            while(s[cur + cons] == s[pre + cons]) cons++;
            res[ rank[i] - 1 ] = cons;
            cons = max<int>(0, cons - 1);
        }
        return res;
    }
};

const int SIZE = 1 << 18;
struct SegmentTreeMin {
    int node[2 * SIZE];
    SegmentTreeMin() {
        fill(node, node + 2*SIZE, INF);
    }
    void update(int x, int val) {
        x += SIZE - 1;
        node[x] = min(node[x], val);
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = min(node[2*x+1], node[2*x+2]);
        }
    }
    int query(int a, int b, int l=0, int r=SIZE, int k=0) {
        if(b <= l or r <= a) return INF;
        if(a <= l and r <= b) return node[k];
        int mid = (l + r) / 2;
        int vl = query(a, b, l, mid, 2*k+1);
        int vr = query(a, b, mid, r, 2*k+2);
        return min(vl, vr);
    }
};

struct SegmentTreeMax {
    int node[2 * SIZE];
    SegmentTreeMax() {
        fill(node, node + 2*SIZE, -INF);
    }
    void update(int x, int val) {
        x += SIZE - 1;
        node[x] = max(node[x], val);
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = max(node[2*x+1], node[2*x+2]);
        }
    }
    int query(int a, int b, int l=0, int r=SIZE, int k=0) {
        if(b <= l or r <= a) return -INF;
        if(a <= l and r <= b) return node[k];
        int mid = (l + r) / 2;
        int vl = query(a, b, l, mid, 2*k+1);
        int vr = query(a, b, mid, r, 2*k+2);
        return max(vl, vr);
    }
};

SegmentTreeMin segMin;
SegmentTreeMax segMax;
 
signed main() {
    string s; cin >> s;
    SuffixArray sa(s);
    int L = s.length();
    for(int i=0; i<s.length() + 1; i++) {
        int idx = sa.getIdx(i);
        segMin.update(i, idx);
        segMax.update(i, idx);
    }

    int N; cin >> N;
    char big = 'z' + 1;
    for(int i=0; i<N; i++) {
        string pref, suf; cin >> pref >> suf;
        int ansL, ansR, lp = pref.size(), ls = suf.size();
        {
            int vl = sa.binary_search_less(pref);
            pref += big;
            int vr = sa.binary_search_greater(pref);

            vl++;
            if(vr == -1) vr = L+1;
            ansL = segMin.query(vl, vr);
        }

        {
            int vl = sa.binary_search_less(suf);
            suf += big;
            int vr = sa.binary_search_greater(suf);

            vl++;
            if(vr == -1) vr = L+1;
            ansR = segMax.query(vl, vr);
        }

        int pr = ansL + lp - 1;
        int sr = ansR + ls - 1;
        if(pr > sr or ansR < ansL) {
            cout << 0 << endl;
        }
        else {
            cout << ansR - ansL + ls << endl;
        }
    }
    return 0;
}