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;
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; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(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> dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;

const int MOD = 1000000000 + 7;

enum {
    NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU
};

class SuccinctBitVector {
private:
    const uint64_t size;                // ビットベクトルのサイズ
    const uint32_t blockBitNum = 64;
    std::vector<uint64_t> B;            // ビットベクトル

    const uint32_t LEVEL_L = 65536;
    const uint32_t LEVEL_S = 256;
    std::vector<uint64_t> L;            // 大ブロック
    std::vector<uint16_t> S;            // 小ブロック

    uint64_t numOne = 0;                // 1bitの数

public:
    explicit SuccinctBitVector(uint64_t n) : size(n) {
        const uint64_t s = (n + blockBitNum - 1) / blockBitNum + 1;   // ceil(n, blockSize)
        this->B.assign(s, 0);
        this->L.assign(n / LEVEL_L + 1, 0);
        this->S.assign(n / LEVEL_S + 1, 0);
    }

    // B[pos] = bit
    void setBit(uint64_t bit, uint64_t pos){
        assert(bit == 0 or bit == 1);
        assert(pos < this->size);

        const uint64_t blockPos = pos / blockBitNum;
        const uint64_t offset = pos % blockBitNum;
        if (bit == 1) { B.at(blockPos) |= (1LLU << offset); }
        else          { B.at(blockPos) &= (~(1LLU << offset)); }
    }

    // B[pos]
    uint64_t access(uint64_t pos) {
        assert(pos < this->size);
        const uint64_t blockPos = pos / blockBitNum;
        const uint64_t offset   = pos % blockBitNum;
        return ((B.at(blockPos) >> offset) & 1);
    }

    void build(){
        uint64_t num = 0;
        for (uint64_t i = 0; i <= size; i++){
            if (i % LEVEL_L == 0) {
                L.at(i / LEVEL_L) = num;
            }
            if (i % LEVEL_S == 0) {
                S.at(i / LEVEL_S) = num - L.at(i / LEVEL_L);
            }
            if (i != size and i % blockBitNum == 0) {
                num += this->popCount(this->B.at(i / blockBitNum));
            }
        }
        this-> numOne = num;
    }

    // B[0, pos)のbitの数
    uint64_t rank(uint64_t bit, uint64_t pos) {
        assert(bit == 0 or bit == 1);
        assert(pos <= this->size);

        if (bit) { return rank1(pos); }
        else     { return pos - rank1(pos); }
    }

    // rank番目のbitの位置 + 1(rankは1-origin)
    uint64_t select(const uint64_t bit, const uint64_t rank) {
        assert(bit == 0 or bit == 1);
        assert(rank > 0);
        if (bit == 0 and rank > this->size - this-> numOne) { return NOTFOUND; }
        if (bit == 1 and rank > this-> numOne)              { return NOTFOUND; }

        // 大ブロックL内を検索
        uint64_t large_idx = 0;
        {
            uint64_t left = 0;
            uint64_t right = L.size();
            while (right - left > 1) {
                uint64_t mid = (left + right) / 2;
                uint64_t r = L.at(mid);
                r = (bit) ? r : mid * LEVEL_L - L.at(mid);

                if (r < rank) {
                    left = mid;
                    large_idx = mid;
                } else {
                    right = mid;
                }
            }
        }

        // 小ブロックS内を検索
        uint64_t small_idx = (large_idx * LEVEL_L) / LEVEL_S;
        {
            uint64_t left = (large_idx * LEVEL_L) / LEVEL_S;
            uint64_t right = std::min(((large_idx  + 1) * LEVEL_L) / LEVEL_S, S.size());
            while (right - left > 1) {
                uint64_t mid = (left + right) / 2;
                uint64_t r = L.at(large_idx) + S.at(mid);
                r = (bit) ? r :mid * LEVEL_S - r;

                if (r < rank) {
                    left = mid;
                    small_idx = mid;
                } else {
                    right = mid;
                }
            }
        }

        // Bをブロック単位で順番に探索
        uint64_t rank_pos = 0;
        {
            const uint64_t begin_block_idx = (small_idx * LEVEL_S) / blockBitNum;
            uint64_t total_bit = L.at(large_idx) + S.at(small_idx);
            if (bit == 0) {
                total_bit = small_idx * LEVEL_S - total_bit;
            }
            for (uint64_t i = 0;; ++i) {
                uint64_t b = popCount(B.at(begin_block_idx + i));
                if (bit == 0) {
                    b = blockBitNum - b;
                }
                if (total_bit + b >= rank) {
                    uint64_t block = (bit) ? B.at(begin_block_idx + i) : ~B.at(begin_block_idx + i);
                    rank_pos = (begin_block_idx + i) * blockBitNum + selectInBlock(block, rank - total_bit);
                    break;
                }
                total_bit += b;
            }
        }

        return rank_pos + 1;
    }

    uint64_t getNumOne() const {
        return numOne;
    }

    void debug() {
        std::cout << "LEVEL_L(" << L.size() << ")" << std::endl;
        for (uint64_t i = 0 ; i < L.size(); ++i) {
            std::cout << L.at(i) << ", ";
        }
        std::cout << std::endl;
        std::cout << "LEVEL_S(" << S.size() << ")" << std::endl;
        for (uint64_t i = 0 ; i < S.size(); ++i) {
            std::cout << S.at(i) << ", ";
        }
        std::cout << std::endl;
    }

private:
    uint64_t rank1(uint64_t pos) {
        uint64_t rank = L.at(pos / LEVEL_L) + S.at(pos / LEVEL_S);

        const uint64_t begin = (pos / LEVEL_S) * LEVEL_S / blockBitNum;
        const uint64_t end = pos / blockBitNum;
        for (uint64_t i = begin; i < end; ++i) {
            rank += popCount(this->B.at(i));
        }
        const uint64_t remain = (pos % LEVEL_S) % blockBitNum;
        rank += popCount(this->B.at(end) & ((1LLU << remain) - 1));

        return rank;
    }

    uint64_t popCount(uint64_t x) {
        x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
        x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
        x = x + (x >>  8);
        x = x + (x >> 16);
        x = x + (x >> 32);
        return x & 0x7FLLU;
    }

    uint64_t selectInBlock(uint64_t x, uint64_t rank) {
        uint64_t x1 = x - ((x & 0xAAAAAAAAAAAAAAAALLU) >> 1);
        uint64_t x2 = (x1 & 0x3333333333333333LLU) + ((x1 >> 2) & 0x3333333333333333LLU);
        uint64_t x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;

        uint64_t pos = 0;
        for (;;  pos += 8){
            uint64_t rank_next = (x3 >> pos) & 0xFFLLU;
            if (rank <= rank_next) break;
            rank -= rank_next;
        }

        uint64_t v2 = (x2 >> pos) & 0xFLLU;
        if (rank > v2) {
            rank -= v2;
            pos += 4;
        }

        uint64_t v1 = (x1 >> pos) & 0x3LLU;
        if (rank > v1){
            rank -= v1;
            pos += 2;
        }

        uint64_t v0  = (x >> pos) & 0x1LLU;
        if (v0 < rank){
            rank -= v0;
            pos += 1;
        }

        return pos;
    }
};

class WaveletMatrix {
private:
    std::vector<SuccinctBitVector> bit_arrays;
    std::vector<uint64_t> begin_one;               // 各bitに着目したときの1の開始位置
    std::map<uint64_t, uint64_t> begin_alphabet;   // 最後のソートされた配列で各文字の開始位置

    uint64_t n;                                    // 与えられた配列のサイズ
    uint64_t num_of_alphabet;                      // 文字数
    uint64_t num_of_bit;                           // 文字を表すのに必要なbit数

public:
    WaveletMatrix () {

    }

    void build(const std::vector<uint64_t> &array) {
        assert(array.size() > 0);
        n = array.size();
        num_of_alphabet =  *max_element(array.begin(), array.end()) + 1;
        num_of_bit = get_num_of_bit(num_of_alphabet);
        if (num_of_bit == 0) {
            num_of_bit = 1;
        }

        for (uint64_t i = 0; i < num_of_bit; ++i) {
            SuccinctBitVector sv(n);
            bit_arrays.push_back(sv);
        }
        this->begin_one.resize(num_of_bit);

        std::vector<uint64_t> v(array);
        for (uint64_t i = 0; i < num_of_bit; ++i) {

            std::vector<uint64_t> temp;
            // 0をtempにいれてく
            for (uint64_t j = 0; j < v.size(); ++j) {
                uint64_t c = v.at(j);
                uint64_t bit = (c >> (num_of_bit - i - 1)) & 1;  //　上からi番目のbit
                if (bit == 0) {
                    temp.push_back(c);
                    bit_arrays.at(i).setBit(0, j);
                }
            }

            this->begin_one.at(i) = temp.size();

            // 1をtempにいれてく
            for (uint64_t j = 0; j < v.size(); ++j) {
                uint64_t c = v.at(j);
                uint64_t bit = (c >> (num_of_bit - i - 1)) & 1;  //　上からi番目のbit
                if (bit == 1) {
                    temp.push_back(c);
                    bit_arrays.at(i).setBit(1, j);
                }
            }

            bit_arrays.at(i).build();
            v = temp;
        }

        // ソートされた配列内での各文字の位置を取得
        for (int i = v.size() - 1; i >= 0; --i) {
            this->begin_alphabet[v.at(i)] = i;
        }
    }

    // v[pos]
    uint64_t access(uint64_t pos) {
        if (pos >= this->n) { return NOTFOUND; }

        uint64_t c = 0;
        for (uint64_t i = 0; i < bit_arrays.size(); ++i) {
            uint64_t bit = bit_arrays.at(i).access(pos);   // もとの数値がのi番目のbit
            c = (c <<= 1) | bit;
            pos = bit_arrays.at(i).rank(bit, pos);
            if (bit) {
                pos += this->begin_one.at(i);
            }
        }
        return c;
    }

    // i番目のcの位置 + 1を返す。rankは1-origin
    uint64_t select(uint64_t c, uint64_t rank) {
        assert(rank > 0);
        if (c >= num_of_alphabet) {
            return NOTFOUND;
        }
        if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {
            return NOTFOUND;
        }

        uint64_t index = this->begin_alphabet.at(c) + rank;
        for (uint64_t i = 0; i < bit_arrays.size(); ++i){
            uint64_t bit = ((c >> i) & 1);      // 下からi番目のbit
            if (bit == 1) {
                index -= this->begin_one.at(num_of_bit - i - 1);
            }
            index = this->bit_arrays.at(num_of_bit - i - 1).select(bit, index);
        }
        return index;
    }

    // v[begin_pos, end_pos)で最大値のindexを返す
    uint64_t maxRange(uint64_t begin_pos, uint64_t end_pos) {
        return quantileRange(begin_pos, end_pos, end_pos - begin_pos - 1);
    }

    // v[begin_pos, end_pos)で最小値のindexを返す
    uint64_t minRange(uint64_t begin_pos, uint64_t end_pos) {
        return quantileRange(begin_pos, end_pos, 0);
    }

    // v[begin_pos, end_pos)でk番目に小さい数値のindexを返す(kは0-origin)
    // つまり小さい順に並べてk番目の値
    uint64_t quantileRange(uint64_t begin_pos, uint64_t end_pos, uint64_t k) {
        if ((end_pos > n || begin_pos >= end_pos) || (k >= end_pos - begin_pos)) {
            return NOTFOUND;
        }

        uint64_t val = 0;
        for (uint64_t i = 0; i < num_of_bit; ++i) {
            uint64_t num_of_zero_begin = bit_arrays.at(i).rank(0, begin_pos);
            uint64_t num_of_zero_end = bit_arrays.at(i).rank(0, end_pos);
            uint64_t num_of_zero = num_of_zero_end - num_of_zero_begin;     // beginからendまでにある0の数
            uint64_t bit = (k < num_of_zero) ? 0 : 1;                       // k番目の値の上からi番目のbitが0か1か

            if (bit) {
                k -= num_of_zero;
                begin_pos = this->begin_one.at(i) + begin_pos - num_of_zero_begin;
                end_pos = this->begin_one.at(i) + end_pos - num_of_zero_end;
            }
            else {
                begin_pos = num_of_zero_begin;
                end_pos = num_of_zero_begin + num_of_zero;
            }

            val = ((val << 1) | bit);
        }

        uint64_t rank = begin_pos + k - this->begin_alphabet.at(val) + 1;
        return select(val, rank) - 1;
    }

    // v[0, pos)のcの数
    uint64_t rank(uint64_t c, uint64_t pos) {
        assert(pos < n);
        if (c >= num_of_alphabet) {
            return 0;
        }
        if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {
            return 0;
        }

        for (uint64_t i = 0; i < num_of_bit; ++i) {
            uint64_t bit = (c >> (num_of_bit - i - 1)) & 1;  // 上からi番目のbit
            pos = bit_arrays.at(i).rank(bit, pos);               // cのi番目のbitと同じ数値の数
            if (bit) {
                pos += this->begin_one.at(i);
            }
        }

        uint64_t begin_pos = this->begin_alphabet.at(c);
        return pos - begin_pos;
    }

    // v[0, pos)でcより小さい文字の数
    uint64_t rankLessThan(uint64_t c, uint64_t pos) {
        uint64_t rank_less_than = 0, rank_more_than = 0, rank = 0;
        rankAll(c, 0, pos, rank, rank_less_than, rank_more_than);
        return rank_less_than;
    }

    // v[0, pos)でcより大きい文字の数
    uint64_t rankMoreThan(uint64_t c, uint64_t pos) {
        uint64_t rank_less_than = 0, rank_more_than = 0, rank = 0;
        rankAll(c, 0, pos, rank, rank_less_than, rank_more_than);
        return rank_more_than;
    }

    // v[begin_pos, end_pos)でcと同じ値の数、cより小さい値の数、cより大きい値の数を求める
    void rankAll(uint64_t c, uint64_t begin_pos, uint64_t end_pos, uint64_t &rank, uint64_t &rank_less_than, uint64_t &rank_more_than) {
        if (c >= num_of_alphabet || begin_pos >= n || end_pos > n) {
            rank_less_than = NOTFOUND;
            rank_more_than = NOTFOUND;
            rank           = NOTFOUND;
            return;
        }
        rank_less_than = 0;
        rank_more_than = 0;
        rank = 0;

        if (begin_pos >= end_pos) {
            return;
        }

        std::vector<uint64_t> more_and_less(2, 0);
        for (uint64_t i = 0; i < num_of_bit; ++i) {
            const uint64_t bit = (c >> (num_of_bit - i - 1)) & 1;

            const uint64_t range_bits = end_pos - begin_pos;
            const uint64_t begin_zero = bit_arrays.at(i).rank(0, begin_pos);
            const uint64_t end_zero = bit_arrays.at(i).rank(0, end_pos);

            if (bit) {
                begin_pos += this->begin_one.at(i) - begin_zero;
                end_pos += this->begin_one.at(i) - end_zero;
            } else {
                begin_pos = begin_zero;
                end_pos = end_zero;
            }
            more_and_less.at(bit) += range_bits - (end_pos - begin_pos);
        }

        rank_less_than = more_and_less.at(1);
        rank_more_than = more_and_less.at(0);
        rank = end_pos - begin_pos;
    }

    // T[s1, e1)で出現回数が多い順にk個の値を返す
    std::vector<std::pair<uint64_t, uint64_t>> topk(uint64_t s, uint64_t e, uint64_t k) {
        assert(s < e);
        std::vector<std::pair<uint64_t, uint64_t>> result;

        auto c = [](const std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t> &l, const std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t> &r) {
            // width
            if (std::get<0>(l) != std::get<0>(r)) {
                return std::get<0>(l) < std::get<0>(r);
            }
            // depth
            if (std::get<3>(l) != std::get<3>(r)) {
                return std::get<3>(l) > std::get<3>(r);
            }
            // value
            if (std::get<4>(l) != std::get<4>(r)) {
                return std::get<4>(l) > std::get<4>(r);
            }
            return true;
        };

        std::priority_queue<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>, std::vector<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>>, decltype(c)> que(c);  // width, left, right, depth, value
        que.push(std::make_tuple(e - s, s, e, 0, 0));

        while (not que.empty()) {
            auto element = que.top(); que.pop();
            uint64_t width, left, right, depth, value;
            std::tie(width, left, right, depth, value) = element;

            if (depth >= this->num_of_bit) {
                result.emplace_back(std::make_pair(value, right - left));
                if (result.size() >= k) {
                    break;
                }
                continue;
            }

            // 0
            const uint64_t left0 = this->bit_arrays.at(depth).rank(0, left);
            const uint64_t right0 = this->bit_arrays.at(depth).rank(0, right);
            if (left0 < right0) {
                que.push(std::make_tuple(right0 - left0, left0, right0, depth + 1, value));
            }

            // 1
            const uint64_t left1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, left);
            const uint64_t right1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, right);
            if (left1 < right1) {
                que.push(std::make_tuple(right1 - left1, left1, right1, depth + 1, value | (1 << num_of_bit - depth - 1)));
            }
        }

        return result;

    };

    // T[s1, e1)とT[s2, e2)に共通して出現する要素を求める
    std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> intersect(uint64_t _s1, uint64_t _e1, uint64_t _s2, uint64_t _e2) {
        assert(_s1 < _e1);
        assert(_s2 < _e2);

        std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> intersection;

        std::queue<std::tuple<uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t>> que; // s1, e1, s2, e2, depth, value
        que.push(std::make_tuple(_s1, _e1, _s2, _e2, 0, 0));
        while (not que.empty()) {
            auto e = que.front(); que.pop();
            uint64_t s1, e1, s2, e2, depth, value;
            std::tie(s1, e1, s2, e2, depth, value) = e;

            if (depth >= this->num_of_bit) {
                intersection.emplace_back(std::make_tuple(value, e1 - s1, e2 - s2));
                continue;
            }

            // 0
            uint64_t s1_0 = this->bit_arrays.at(depth).rank(0, s1);
            uint64_t e1_0 = this->bit_arrays.at(depth).rank(0, e1);
            uint64_t s2_0 = this->bit_arrays.at(depth).rank(0, s2);
            uint64_t e2_0 = this->bit_arrays.at(depth).rank(0, e2);

            if (s1_0 != e1_0 and s2_0 != e2_0) {
                que.push(std::make_tuple(s1_0, e1_0, s2_0, e2_0, depth + 1, value));
            }

            // 1
            uint64_t s1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s1);
            uint64_t e1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e1);
            uint64_t s2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s2);
            uint64_t e2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e2);

            if (s1_1 != e1_1 and s2_1 != e2_1) {
                que.push(std::make_tuple(s1_1, e1_1, s2_1, e2_1, depth + 1, value | (1 << num_of_bit - depth - 1)));
            }
        }

        return intersection;
    };

private:
    uint64_t get_num_of_bit(uint64_t x) {
        if (x == 0) return 0;
        x--;
        uint64_t bit_num = 0;
        while (x >> bit_num) {
            ++bit_num;
        }
        return bit_num;
    }


};


class SuffixArray {
    int n, k;
    std::vector<int> rank;
    std::vector<int> tmp;

public:
    const std::string s;
    std::vector<uint64_t> sa;
    std::vector<int> lcp;


public:
    SuffixArray(const std::string &s) : n(s.size()), s(s) {
        sa.assign(n + 1, 0);
        lcp.assign(n, 0);
        rank.assign(n + 1, 0);
        tmp.assign(n + 1, 0);
    }

    void build() {
        this->construct_sa();
        this->construct_lcp();
    }

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

    // sa上でのpatternの範囲(閉区間)
    pair<int, int> range(const string &pattern) {
        return make_pair(lower_bound(pattern), upper_bound(pattern));
    };

    // sa上で最初にpatternが現れる位置
    int lower_bound(const string &pattern) {
        int left = -1, right = n;
        while (right - left > 1) {
            int c = (left + right) / 2;
            int ret = s.compare(sa[c], pattern.length(), pattern);
            // patternが大きい
            if (ret >= 0) {
                 right = c;
            }
            else {
                left = c;
            }
        }
        if (s.compare(sa[right], pattern.length(), pattern) == 0) {
            return right;
        }
        return -1;
    }

    // sa上で最後にpatternが現れる位置
    int upper_bound(const string &pattern) {
        int left = -1, right = n + 1;
        while (right - left > 1) {
            int c = (left + right) / 2;
            int ret = s.compare(sa[c], pattern.length(), pattern);
            // patternが小さい
            if (ret <= 0) {
                left = c;
            }
            else {
                right = c;
            }
        }
        if (s.compare(sa[left], pattern.length(), pattern) == 0) {
            return left;
        }
        return -1;
    }

    void debug() {
        std::cout << "idx lcp sa sa[i]" << std::endl;
        for (int i = 0; i < n; ++i) {
            std::cout << i << " " << lcp[i] << " " << sa[i] << " " << s.substr(sa[i]) << std::endl;
        }
    }

private:
    struct compare {
        compare(const SuffixArray &sa) : sa(sa) {}
        const SuffixArray &sa;

        // (rank[i], rank[i + k])と(rank[j], rank[j + 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 + sa.k <= sa.n ? sa.rank[i + sa.k] : -1;
                int rj = j + sa.k <= sa.n ? sa.rank[j + sa.k] : -1;
                return ri < rj;
            }
        }
    };

    void construct_sa() {
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }
        // k文字についてソートされているところから、2k文字でソートする
        for (k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), compare(*this));
            // いったんtmpに次のランクを計算し、それからrankに移す
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare(*this).operator()(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) {
                rank[i] = tmp[i];
            }
        }
    }

    void construct_lcp() {
        for (int i = 0; i <= n; i++) {
            rank[sa[i]] = i;
        }
        int h = 0;
        lcp[0] = 0;
        for (int i = 0; i < n; i++) {
            // 文字列中での位置iの接尾辞と、接尾辞配列中でその1つ前の接尾辞のLCPを求める
            int j = sa[rank[i] - 1];
            // hを先頭の分1減らし、後ろが一致しているだけ増やす
            if (h > 0) {
                h--;
            }
            for (; j + h < n and i + h < n; h++) {
                if (s[j + h] != s[i + h]) {
                    break;
                }
            }
            lcp[rank[i] - 1] = h;
        }
    }
};

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

    string S;
    cin >> S;

    SuffixArray sa(S);
    sa.build();

    WaveletMatrix wm;
    wm.build(sa.sa);

    int M;
    cin >> M;
    FOR(i, 0, M) {
        string X, Y;
        cin >> X >> Y;

        auto x_range = sa.range(X);
        auto y_range = sa.range(Y);
        if (x_range.first == -1 or x_range.second == -1 or y_range.first == -1 or y_range.second == -1) {
            print(0);
            continue;
        }

        int x_begin = sa.sa[wm.minRange(x_range.first, x_range.second + 1)];
        int x_end = x_begin + X.size()  - 1;
        int y_begin = sa.sa[wm.maxRange(y_range.first, y_range.second + 1)];
        int y_end = y_begin + Y.size() - 1;

        if (y_end < x_end) {
            print(0);
            continue;
        }

        print(y_end - x_begin + 1);
    }


    return 0;
}