#include<bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Ford(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define N 1000005
using namespace std;
int n, q;
string s[N];
int stranform(char x)
{
if (x == 'A') return 0;
if (x == 'C') return 1;
if (x == 'G') return 2;
return 3;
}
struct Trie
{
struct Node
{
Node* c[4];
int l, r;
Node()
{
For (i, 0, 3) c[i] = 0;
l = 2e9;
r = 0;
}
};
Node* root;
Trie()
{
root = new Node();
}
void add (string s, int id)
{
Node* p = root;
For (i, 0, (int) s.size() - 1)
{
int x = stranform (s[i]);
if (!p->c[x])
p->c[x] = new Node();
p = p->c[x];
if (id < p->l) p->l = id;
if (id > p->r) p->r = id;
}
}
ii get (string s)
{
Node* p = root;
For (i, 0, (int) s.size() - 1)
{
int x = stranform(s[i]);
if (!p->c[x])
return {2e9, 2e9};
p = p->c[x];
}
return {p->l, p->r};
}
};
struct RTrie
{
struct Node
{
Node* c[4];
vector<int> id;
Node()
{
For (i, 0, 3) c[i] = 0;
}
};
Node* root;
RTrie()
{
root = new Node();
}
void add (string s, int id)
{
reverse (s.begin(), s.end() );
Node* p = root;
For (i, 0, (int) s.size() - 1)
{
int x = stranform (s[i]);
if (!p->c[x])
p->c[x] = new Node();
p = p->c[x];
p->id.push_back (id);
}
}
int get (string s, ii k)
{
int l = k.fi, r = k.se;
if (l == r && l == 2e9)
return 0;
Node* p = root;
For (i, 0, (int) s.size() - 1)
{
int x = stranform (s[i]);
if (!p->c[x])
return 0;
p = p->c[x];
}
return upper_bound (p->id.begin(), p->id.end(), r) - lower_bound (p->id.begin(), p->id.end(), l);
}
};
int main()
{
ios_base::sync_with_stdio (0);
cin.tie (NULL);
cout.tie (NULL);
cin >> n >> q;
For (i, 1, n) cin >> s[i];
sort (s + 1, s + 1 + n);
Trie t1;
RTrie t2;
For (i, 1, n)
{
t1.add (s[i], i);
t2.add (s[i], i);
}
while (q--)
{
string p, q;
cin >> p >> q;
reverse (q.begin(), q.end() );
cout << t2.get (q, t1.get (p) ) << "\n";
}
return 0;
}
