#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9
const int MAX = 1e4 + 5, MAX2 = 500 + 5, B = 61, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
int n, q;
string s;
string t[MAX];
map<pii, int> mp;
pii pre[MAX2];
int dp[MAX2][MAX2];
pii P[(int)5e5 + 5];
pii invP[(int)5e5 + 5];
int binpow(int a, int b, int m){
if(b == 0) return 1;
if(b & 1) return binpow(a, b - 1, m) % m * a % m;
return binpow(a * a % m, b / 2, m) % m;
}
int inv(int a, int m){
return binpow(a, m - 2, m);
}
pii calc(int l, int r){
return {(pre[r].first - pre[l - 1].first + 2 * MOD1) % MOD1 * invP[l - 1].first % MOD1,
(pre[r].second - pre[l - 1].second + 2 * MOD2) % MOD2 * invP[l - 1].second % MOD2};
}
void solve(){
P[0]= {1, 1};
invP[0] = {1, 1};
for(int i = 1; i <= 5e5; i++){
P[i].first = P[i - 1].first * B % MOD1;
P[i].second = P[i - 1].second * B % MOD2;
invP[i].first = invP[i - 1].first * inv(B, MOD1) % MOD1;
invP[i].second = invP[i - 1].second * inv(B, MOD2) % MOD2;
}
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> t[i];
pii H = {0, 0};
for(int j = 0; j < t[i].size(); j++){
H.first = (H.first + (t[i][j] - 'a' + 1) * P[j].first % MOD1) % MOD1;
H.second = (H.second + (t[i][j] - 'a' + 1) * P[j].second % MOD2) % MOD2;
mp[H] = 1;
}
}
cin >> s;
int L = s.size();
for(int i = 1; i <= L; i++){
pre[i].first = (pre[i - 1].first + (s[i - 1] - 'a' + 1) * P[i - 1].first % MOD1) % MOD1;
pre[i].second = (pre[i - 1].second + (s[i - 1] - 'a' + 1) * P[i - 1].second % MOD2) % MOD2;
}
for(int sz = 1; sz <= L; sz++){
for(int i = 1; i + sz - 1 <= L; i++){
int j = i + sz - 1;
dp[i][j] = oo;
if(mp.count(calc(i, j))){
dp[i][j] = 1;
continue;
}
for(int k = i; k <= j - 1; k++){
dp[i][j] = min(dp[i][k] + dp[k + 1][j], dp[i][j]);
}
}
}
while(q--){
int l, r; cin >> l >> r;
l++;
if(dp[l][r] == oo) dp[l][r] = -1;
cout << dp[l][r] << '\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while(t--){
solve();
}
}
