zzz

#include <bits/stdc++.h>
#define MAX 100007

using namespace std;
int z[MAX], tam;
string txt;
int func(){
    int l = 0, r = 0;
    for(int i = 0; i < tam; i++){
        if(i > r){
            l = r = i;
            while(r < tam && txt[r] == txt[r-l]) r++;
            z[i] = r-l; r--;
        }else{
            int k = i-l;
            if(z[k] < k-i+1) z[i] = z[k];
            else{
                l = i;
                while(r < tam && txt[r] == txt[r-l]) r++;
                z[i] = r-l; r--;
            }
        }
    }
    z[0] = tam;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int num; cin >> num;
    while(num--){
        cin >> txt;
        tam = txt.size();
        reverse(txt.begin(), txt.end());
        func();
        int cases; cin >> cases;
        while(cases--){
            int aux; cin >> aux;
            cout << z[tam-aux] << endl;;
        }
    }
    return 0;
}