Untitled

// Author: _Sherbiny

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define endl '\n'
#define int ll
//====================//

struct SuffixAutomaton {
    static const int A = 26;

    struct State {
        int len = 0, lnk = -1, firstPos = 0;
        bool isClone = 0;
        array<int, A> nxt;
        State() { nxt.fill(-1); }
    };

    vector<vector<int>> adj;
    vector<State> t{{}};
    int lst = 0;

    SuffixAutomaton(string &s) {
        for(char &ch: s) insert(ch);
    }

    void insert(int ch) {
        int c = ch - 'a', me = t.size(), p = lst;
        t.push_back({});
        t[me].len = t[p].len + 1;
        t[me].firstPos = t[me].len - 1;
        t[me].lnk = 0;
        lst = me;

        while(~p && t[p].nxt[c] == -1) {
            t[p].nxt[c] = me;
            p = t[p].lnk;
        }

        if(p == -1) return;

        int q = t[p].nxt[c];
        if(t[q].len == t[p].len + 1) {
            t[me].lnk = q;
            return;
        }

        int clone = t.size();
        t.push_back(t[q]);

        t[clone].len = t[p].len + 1;
        t[clone].isClone = 1;

        while (~p && t[p].nxt[c] == q) {
            t[p].nxt[c] = clone;
            p = t[p].lnk;
        }

        t[q].lnk = t[me].lnk = clone;
    }

    int move(int v, char &c) { return ~v? t[v].nxt[c - 'a'] : -1; }

    void pre() {
        adj.resize(size(t));
        for(int i = 1; i < size(t); ++i)
            adj[t[i].lnk].push_back(i);
    }

    void dfs(int u, vector<int> &occ) {
        if(u == -1) return;
        if(!t[u].isClone) occ.push_back(t[u].firstPos);
        for(int &v: adj[u]) dfs(v, occ);
    }
};

void magic() {
    string s; cin >> s;
    SuffixAutomaton sa(s);
    sa.pre();

    int m; cin >> m;
    map<string, int> id;
    vector<int> to(m), len(m), ans(m), st(m);
    vector<vector<int>> occ(m);

    for(int i = 0; i < m; ++i) {
        string t; cin >> t;
        if(id.count(t)) {
            to[i] = id[t];
            continue;
        }

        id[t] = size(id);
        to[i] = id[t], len[to[i]] = size(t);

        int u = 0;
        for(char &ch: t) u = sa.move(u, ch);
        st[to[i]] = u;
    }

    for(int i = 0; i < size(id); ++i) {
        vector<int> me;
        sa.dfs(st[i], me);
        sort(me.begin(), me.end());

        int r = 0;
        for(int j = 0; j < size(me); ++j) {
            while(r < size(me) && me[r] - len[i] + 1 <= me[j]) ++r;
            ans[i] = max(ans[i], min((int)size(me) - r, j + 1));
        }
    }

    for(int i = 0; i < m; ++i)
        cout << ans[to[i]] << endl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t = 1;
    cin >> t;
    while (t--) magic();
}