//In the name of God
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N = 5e5 + 100;
const lli mod = 1e9 + 7;
const lli INF = 1e18;
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define FOR(x,y) for(lli x = 0 ;x < y; x++)
#define FORS(x,y) for(lli x = 1 ;x <= y; x++)
#define debug(x) cerr<<(#x)<<" "<<x<<endl
#define all(x) x.begin(),x.end()
struct Trie{
lli nxt[N][26];
void build(){
FOR(i,N)FOR(j,26)nxt[i][j] = -1;
}
lli vercnt = 1;
void add(string s){
lli v = 1;
FOR(i,(lli)s.size()){
if(nxt[v][(s[i]-'a')] == -1)
nxt[v][(s[i]-'a')] = ++vercnt;
v = nxt[v][(s[i]-'a')];
}
}
bool find(string s){
lli v = 1;
FOR(i,(lli)s.size()){
if(nxt[v][(s[i]-'a')] == -1)return 0;
v = nxt[v][(s[i]-'a')];
}
return 1;
}
};
Trie t;
lli n,m;
lli dp[1000][1000];bool fo[1000][1000];
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
t.build();
FORS(i,n){
string s;
cin>>s;
t.add(s);
}
string S;
cin>>S;
S = '#' + S;
lli L = S.size()-1;
FORS(l,L){
string s = "";
for(lli r = l;r <= L ;r ++){
s += S[r];
fo[l][r] = t.find(s);
}
}
FORS(l,L){
for(lli r = l; r <= L; r ++){
dp[l][r] = INF;
if(fo[l][r])dp[l][r] = 1;
}
}
for(lli l = L; l > 0; l --){
for(lli r = l; r <=L; r ++){
for(lli k = l; k < r; k ++)
if(fo[l][k])
dp[l][r] = min(dp[l][r],dp[k+1][r] + 1);
}
}
while(m --){
lli l,r;
cin>>l>>r;
l ++;
if(dp[l][r] == INF)dp[l][r] = -1;
cout<<dp[l][r]<<endl;
}
}
