#include #define endl '\n' using namespace std; const long long base = 1e9 + 1, mod = 1e9 + 9, maxN = 5 * 1e5 + 5; long long q, h, h1, ans, basePows[maxN], hashes[5005]; string s, t, p; long long stringHash(string k) { long long ret = 0; for(int i = 0; i < k.size(); i++) { ret = ((long long)ret * base + k[i]) % mod; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); freopen("clown.in", "r", stdin); freopen("clown.out", "w", stdout); cin>>s>>q; basePows[0] = 1; for(int i = 1; i < s.size(); i++) { basePows[i] = (basePows[i - 1] * base) % mod; } memset(hashes, -1, sizeof(hashes)); for(int i = 0; i < q; i++) { ans = 0; cin>>t; h = stringHash(t); p = s.substr(0, t.size()); if(hashes[t.size()] == -1) h1 = stringHash(p); else h1 = hashes[t.size()]; if(h == h1) ans++; long long basePow = basePows[t.size() - 1]; for(int j = t.size(); j < s.size(); j++) { h1 -= ((long long)s[j - t.size()] * basePow) % mod; if(h1 < 0) { h1 += mod; } h1 = (h1 * base + (long long)s[j]) % mod; if(h1 == h) ans++; } cout<