#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
int n, m;
namespace sub12{
const int mod = 1e9 + 33;
const int base = 397;
const int lim = 5e3 + 5;
const int LIM = 2e6 + 5;
int pw[LIM];
vector<int>hash[lim];
int get_hash(int id, int l, int r){
return (ll(hash[id][r]) - 1LL * hash[id][l - 1] * pw[r - l + 1] + 1LL * mod * mod) % mod;
}
void solve(){
for(int i = pw[0] = 1; i < LIM; i++){
pw[i] = 1LL * pw[i - 1] * base % mod;
}
for(int i = 0; i < n; i++){
string s;
cin >> s;
hash[i].emplace_back(0);
for(int j = 0; j < s.size(); j++){
hash[i].emplace_back((1LL * hash[i].back() * base + s[j]) % mod);
}
}
for(int _ = 0; _ < m; _++){
string p, q;
cin >> p >> q;
int ans = 0, P = 0, Q = 0;
for(int i = 0; i < p.size(); i++){
P = (1LL * P * base + p[i]) % mod;
}
for(int i = 0; i < q.size(); i++){
Q = (1LL * Q * base + q[i]) % mod;
}
for(int i = 0; i < n; i++){
if(hash[i].size() > max(p.size(), q.size()) && get_hash(i, 1, p.size()) == P && get_hash(i, int(hash[i].size()) - int(q.size()), int(hash[i].size()) - 1) == Q){
ans++;
}
}
cout << ans << "\n";
}
}
}
namespace sub34{
const int LIM = 2e6 + 5;
const int lim = 2e5 + 5;
void convert(string& s){
for(char& c : s){
if(c == 'A'){
c = 0;
}
else if(c == 'G'){
c = 1;
}
else if(c == 'C'){
c = 2;
}
else{
c = 3;
}
}
}
struct Node{
int child[4];
Node(){
memset(child, -1, sizeof(child));
}
};
struct Trie{
vector<Node>trie;
int time_dfs, low[LIM], tail[LIM];
Trie(){
time_dfs = 0;
trie.emplace_back(Node());
}
void insert(string& s){
int root = 0;
for(char& c : s){
if(trie[root].child[c] == -1){
trie[root].child[c] = trie.size();
trie.emplace_back(Node());
}
root = trie[root].child[c];
}
}
void dfs(int s){
low[s] = ++time_dfs;
for(int i = 0; i < 4; i++){
if(trie[s].child[i] != -1){
dfs(trie[s].child[i]);
}
}
tail[s] = time_dfs;
}
pair<int, int>get_pair(string& s){
int root = 0;
for(char& c : s){
if(trie[root].child[c] == -1){
return make_pair(-1, -1);
}
root = trie[root].child[c];
}
return make_pair(low[root], tail[root]);
}
};
Trie prefix, suffix;
int bit[LIM], ans[lim];
vector<pair<int, int>>query[LIM];
vector<int>point[LIM];
void update(int p){
for(; p < LIM; p += p & -p){
bit[p]++;
}
}
int get(int p){
int ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
void solve(){
vector<string>S(n);
for(string& s : S){
cin >> s;
convert(s);
prefix.insert(s);
reverse(s.begin(), s.end());
suffix.insert(s);
}
prefix.dfs(0);
suffix.dfs(0);
for(int i = 0; i < n; i++){
int y = suffix.get_pair(S[i]).first;
reverse(S[i].begin(), S[i].end());
point[y].emplace_back(prefix.get_pair(S[i]).first);
}
for(int i = 1; i <= m; i++){
string p, q;
cin >> p >> q;
convert(p);
reverse(q.begin(), q.end());
convert(q);
pair<int, int>range_prefix = prefix.get_pair(p), range_suffix = suffix.get_pair(q);
if(range_prefix.first != -1 && range_suffix.first != -1){
query[range_suffix.second].emplace_back(range_prefix.second, i);
query[range_suffix.first - 1].emplace_back(range_prefix.first - 1, i);
query[range_suffix.second].emplace_back(range_prefix.first - 1, -i);
query[range_suffix.first - 1].emplace_back(range_prefix.second, -i);
}
}
memset(ans, 0, sizeof(ans));
memset(bit, 0, sizeof(bit));
for(int i = 1; i < LIM; i++){
for(int& j : point[i]){
update(j);
}
for(auto& [j, index] : query[i]){
if(index < 0){
ans[-index] -= get(j);
}
else{
ans[index] += get(j);
}
}
}
for(int i = 1; i <= m; i++){
cout << ans[i] << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> m;
if(max(n, m) <= 5000){
sub12::solve();
}
else{
sub34::solve();
}
}
