Untitled

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <cassert>
#include <iomanip>
#include <cstring>
#include <stack>
#include <bitset>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

void count_sort(vector<int> &p, vector<int> &c){
    int n = p.size();
    vector<int> cnt(n), pos(n), new_p(n);
    for (auto &x : c){
        cnt[x]++;
    }
    pos[0] = 0;
    for (int i = 1 ; i < n; ++i)
        pos[i] = pos[i - 1] + cnt[i - 1];
    for (auto &x : p){
        int i = c[x];
        new_p[pos[i]] = x;
        pos[i]++;
    }
    p = new_p;
}
vector<int>p, c;

void suffix_array(string s){
    s += '$';
    int n = s.size();
    p.resize(n), c.resize(n);
    {
        vector<pair<char, int>> v(n);
        for (int i = 0 ; i < n; ++i)
            v[i] = make_pair(s[i], i);
        sort(v.begin(), v.end());
        for (int i = 0; i < n; ++i)
            p[i] = v[i].second; /// The ith smallest lexo string starts at index p[i]
        c[p[0]] = 0;
        for (int i = 1; i < n; ++i){
            if (v[i].first == v[i - 1].first)
                c[p[i]] = c[p[i - 1]];
            else
                c[p[i]] = c[p[i - 1]] + 1;
        }
    }
    int k = 0;
    while((1 << k) < n){
        for (int i = 0 ; i < n; ++i)
            p[i] = (p[i] - (1 << k) + n) % n; /// Sort it based on the second;

        count_sort(p, c);
        vector<int>new_c(n);
        new_c[p[0]] = 0;
        for (int i = 1; i < n; ++i){
            pair<int,int> prev = make_pair(c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]);
            pair<int,int> cur = make_pair(c[p[i]], c[(p[i] + (1 << k)) % n]);
            if (cur == prev){
                new_c[p[i]] = new_c[p[i - 1]];
            }
            else new_c[p[i]] = new_c[p[i - 1]] + 1;
        }
        c = new_c;
        ++k;
    }
}


void solve(){
    string s; cin >> s;
    int n = s.size();
    suffix_array(s);
    int q; cin >> q;
    while(q--){
        string t; cin >> t;
        int cur_sz = t.size();
        int l = 1, r = n, mid, ans = n + 1;
        while(l <= r){
            mid = (l + r) >> 1;
            string cur = s.substr(p[mid], min(cur_sz, n - p[mid]));
            if (cur >= t){
                r = mid - 1;
                ans = mid;
            }
            else {
                l = mid + 1;
            }
        }
        l = ans, r = n;
        int fans = 0;
        while (l <= r){
            mid = (l + r) >> 1;
            string cur = s.substr(p[mid], min(cur_sz, n - p[mid]));
            if (cur > t){
                r = mid - 1;
            }
            else {
                fans = mid - ans + 1;
                l = mid + 1;
            }
        }
        cout << fans << '\n';
    }
}

int main(){
    fast;
	int t = 1; //cin >> t;
    for (int i = 1; i <= t; ++i){
        solve();
        if (i != t)
            cout << '\n';
    }
  }