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;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1000000000 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

struct SuffixArray {
    int n, k;
    string text;
    vector<int> sa;
    vector<int> rank;
    vector<int> lcp;

    SuffixArray (const string &s)
    : text(s), n(s.size()), sa(n + 1), rank(n + 1), lcp(n)
    {}

    bool comp(int i, int j) {
        if (rank[i] != rank[j]) return rank[i] < rank[j];
        int ri = i + k <= n ? rank[i + k] : -1;
        int rj = j + k <= n ? rank[j + k] : -1;
        return ri < rj;
    }

    void construct_sa() {
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            rank[i] = i < n ? text[i] : -1;
        }

        for (k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), [&](const int& i, const int& j) {return comp(i, j);});

            vector<int> tmp(n + 1);
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (comp(sa[i - 1], sa[i]) ? 1 : 0);
            }

            for (int i = 0; i <= n; i++) {
                rank[i] = tmp[i];
            }
        }
    }

    void construct_lcp () {
        int h = 0;
        lcp[0] = 0;
        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 (text[j + h] != text[i + h]) break;
            }
            lcp[rank[i] - 1] = h;
        }
    }
    int low_bd(const string &pt) {
        int l = 0, r = n;
        while (r - l > 1) {
            int m = (r + l) / 2;
            int val = text.compare(sa[m], pt.length(), pt);
            if (val < 0) l = m;
            else r = m;
        }
        return r;
    }

    int up_bd(const string &pt) {
        int l = 1, r = n + 1;
        while (r - l > 1) {
            int m = (r + l) / 2;
            int val = text.compare(sa[m], pt.length(), pt);
            if (val <= 0) l = m;
            else r = m;
        }
        return r;
    }

    bool match(const string &pt) {
        int idx = low_bd(pt);
        return text.compare(sa[idx], pt.length(), pt) == 0 ? true : false;
    }

    int count(const string &pt) {
        int l_idx = low_bd(pt);
        if (text.compare(sa[l_idx], pt.length(), pt) != 0) return 0;
        int r_idx = up_bd(pt);
        return r_idx - l_idx;
    }
};
struct segtree {
    int size;
    vector<long long> node;

    segtree (int n) : size(1), node((1 << 19) - 1, LLONG_MAX / 10) {
        while (size < n) size *= 2;
        for (int i = 0; i < 2 * size - 1; i++) node[i] = LLONG_MAX / 10;
    }

    void update(int k, int a) {
        k += size - 1;
        node[k] = a;
        while (k > 0){
            k = (k - 1) / 2;
            node[k] = min(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    long long get_min(int queryL, int queryR, int k = 0, int nodeL = 0, int nodeR = -1) {
        if (nodeR == -1) nodeR = size;
        if (nodeR <= queryL || queryR <= nodeL) return LLONG_MAX / 10;
        if (queryL <= nodeL && nodeR <= queryR) return node[k];
        else{
            int nodeM = (nodeL + nodeR) / 2;
            long long vl = get_min(queryL, queryR, 2 * k + 1, nodeL, nodeM);
            long long vr = get_min(queryL, queryR, 2 * k + 2, nodeM, nodeR);
            return min(vl, vr);
        }
    }
};

string s;
int m;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    int n = s.size();
    string t = s;
    reverse(all(t));
    SuffixArray suf1(s);
    SuffixArray suf2(t);
    suf1.construct_sa();
    suf2.construct_sa();
    segtree seg1(n + 1);
    segtree seg2(n + 1);
    rep2(i, 1, n + 1) {
        seg1.update(i, suf1.sa[i]);
        seg2.update(i, -(n - 1 - suf2.sa[i]));
    }
    cin >> m;
    rep(i, m) {
        string x, y;
        cin >> x >> y;
        reverse(all(y));
        if (!suf1.match(x) || !suf2.match(y)) {
            cout << 0 << endl;
            continue;
        }
        int l1 = suf1.low_bd(x);
        int r1 = suf1.up_bd(x);
        int l2 = suf2.low_bd(y);
        int r2 = suf2.up_bd(y);
        int l = seg1.get_min(l1, r1);
        int r = -seg2.get_min(l2, r2);
        if (l + x.size() > r + y.size()) {
            cout << 0 << endl;
            continue;
        }
        cout << max(0LL, r - l + 1) << endl;
    }
}