#include <iostream> #include <vector> #include <algorithm> using namespace std; int get(char c) { if(c=='A')return 0; if(c=='C')return 1; if(c=='G')return 2; return 3; } const int M=2e6+10,N=1e5+10; string s[N]; int nxt[2][M][4]; vector<int> cur[2][M]; int lst[10]; void insert(string&s,int ind,bool p=0) { int rt=0; cur[p][rt].push_back(ind); for(int i=0;i<s.size();i++) { if(!nxt[p][rt][get(s[i])])nxt[p][rt][get(s[i])]=++lst[p]; rt=nxt[p][rt][get(s[i])]; cur[p][rt].push_back(ind); } } pair<int,int> rg(string& s) { bool p=0; int rt=0; for(int i=0;i<s.size();i++) { if(!nxt[p][rt][get(s[i])]) return {1,0}; rt=nxt[p][rt][get(s[i])]; } return {*begin(cur[p][rt]),*rbegin(cur[p][rt])}; } int count(string& s,int ql,int qr) { bool p=1; int rt=0; for(int i=0;i<s.size();i++) { if(!nxt[p][rt][get(s[i])]) return 0; rt=nxt[p][rt][get(s[i])]; } return upper_bound(begin(cur[p][rt]),end(cur[p][rt]),qr)-lower_bound(begin(cur[p][rt]),end(cur[p][rt]),ql); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=0;i<n;i++)cin>>s[i]; sort(s,s+n); for(int i=0;i<n;i++) { insert(s[i],i); reverse(begin(s[i]),end(s[i])); insert(s[i],i,1); } for(int j=0;j<m;j++) { string p,q; cin>>p>>q; auto rag=rg(p); reverse(begin(q),end(q)); cout<<count(q,rag.first,rag.second)<<endl; } }