//By momo
#include<cstdio>
#include<algorithm>
#define MAXN 10010
using namespace std;
struct doub{ int x, y; doub(){} doub(int _x,int _y){x=_x;y=_y;} }Sa[MAXN];
bool comp( doub a, doub b ){ return a.x < b.x; }
int n, sa[MAXN], ra[MAXN], x[MAXN], y[MAXN], h[MAXN], he[MAXN];
char a[MAXN], b[MAXN];
int st[20][MAXN];
void init(){
for( int i = 0 ; i < n ; i++ ) st[0][i] = he[i];
for( int l = 1 ; l < 15 ; l++ ){
int L = 1<<l;
for( int i = 0 ; i < n-L+1 ; i++ )
st[l][i] = min( st[l-1][i], st[l-1][i+L/2] );
}
}
int LCP( int l, int r ){
if( l == r ) return n-sa[l];
if( l > r ) swap( l, r ); l++;
int L = __lg(r-l+1);
return min( st[L][l], st[L][r-(1<<L)+1] );
}
int main(){
int t; scanf( "%d", &t );
while( t-- ){
scanf( "%s", a ); n = strlen(a);
//GET SA1
for( int i = 0 ; i < n ; i++ ) Sa[i] = db( a[i]-'a', i );
sort( Sa, Sa+n, comp );
//GET RA1
int m = ra[Sa[0].y] = 1;
for( int i = 1 ; i < n ; i++ ) ra[Sa[i].y] = ( Sa[i].x != Sa[i-1].x ) ? ++m : m;
//GET SA & RA
for( int l = 1 ; m < n ; l *= 2 ){ //Half the length of the range
// sort the second object
int yn = 0;
for( int i = n-l ; i < n ; i++ ) y[yn++] = i;
for( int i = 0 ; i < n ; i++ ) if( Sa[i].y >= l ) y[yn++] = Sa[i].y-l;
// sort the first object
for( int i = 0 ; i <= m ; i++ ) x[i] = 0;
for( int i = 0 ; i < n ; i++ ) x[ra[y[i]]]++;
for( int i = 1 ; i < n ; i++ ) x[i] += x[i-1];
for( int i = n-1 ; i >= 0 ; i-- ){
Sa[x[ra[y[i]]]-1] = db( ra[y[i]]*(m+2) + ( y[i] >= n-l ? 0 : ra[y[i]+l] ), y[i] );
x[ra[y[i]]]--;
}
// get ra value
m = ra[Sa[0].y] = 1;
for( int i = 1 ; i < n ; i++ ) ra[Sa[i].y] = ( Sa[i].x != Sa[i-1].x ) ? ++m : m;
}
for( int i = 0 ; i < n ; i++ ) ra[i]--, sa[i] = Sa[i].y;
//GET H
for( int i = 0 ; i < n ; i++ ){
if( ra[i] == 0 ){ h[i] = 0; continue; }
h[i] = ( i == 0 || h[i-1] <= 1 ) ? 0 : h[i-1]-1 ;
int p = sa[ra[i]-1], q = sa[ra[i]], mx = max( p, q );
while( mx+h[i] < n && a[p+h[i]] == a[q+h[i]] ) h[i]++;
}
//GET height
for( int i = 0 ; i < n ; i++ ) he[ra[i]] = h[i];
//GET ST
init();
int q; scanf( "%d", &q );
while( q-- ){
scanf( "%s", b );
int n2 = strlen(b);
int mx, ans, l = 0, r = n-1, mid, s = sa[n-1], i = 0;
while( i < n2 && s+i < n && a[s+i] == b[i] ) i++;
mx = i; ans = r;
while( l < r ){
s = sa[mid=(l+r)/2], i = LCP( mid, ans );
if( i >= mx ){
i = mx; while( i < n2 && s+i < n && a[s+i] == b[i] ) i++;
mx = i, ans = mid;
}
if( mx == n2 ) break;
( s+i == n || a[s+i] < b[i] ) ? l = mid+1 : r = mid;
}
if( mx < n2 ){ puts("0"); continue; }
l = ans; r = n;
while( l < r-1 ) LCP( mid=(l+r)/2, ans ) < n2 ? (r = mid) : (l = mid) ;
int LB = l;
l = -1; r = ans;
while( l < r-1 ) LCP( mid=(l+r)/2, ans ) < n2 ? (l = mid) : (r = mid) ;
printf( "%d\n", LB-r+1 );
}
}
}