#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 10 , Base = 727 , maxl = 20;
int n , L , m , pw[2][maxn] , mod[2] , prehsh[2][maxn] , rr[maxn];
pair<int , int> ar[maxn] , adj[maxl][maxn];
int modit(int ty , int a)
{
if(a >= mod[ty]) return a - mod[ty];
return a;
}
pair<int , int> get(int l , int r)
{
int res[2];
if(l == 0) return make_pair(prehsh[0][r] , prehsh[1][r]);
for(int ty = 0 ; ty < 2 ; ty++)
{
res[ty] = 1LL * prehsh[ty][l - 1] * pw[ty][r - l + 1] % mod[ty];
res[ty] = modit(ty , prehsh[ty][r] + mod[ty] - res[ty]);
}
return make_pair(res[0] , res[1]);
}
int solve(int l , int r)
{
if(adj[maxl - 1][l].S < r) return -1;
int res = 0;
for(int i = maxl - 2 ; i > -1 ; i--) if(adj[i][l].S < r)
{
res |= (1 << i);
l = adj[i][l].F;
}
res++;
return res;
}
int32_t main()
{
fast;
mod[0] = 1e9 + 7;
mod[1] = 998244353;
pw[0][0] = pw[1][0] = 1;
for(int i = 1 ; i < maxn ; i++) for(int ty = 0 ; ty < 2 ; ty++)
pw[ty][i] = 1LL * pw[ty][i - 1] * Base % mod[ty];
cin >> n >> m;
vector <pair<int , int>> vec;
for(int i = 0 ; i < n ; i++)
{
string t; cin >> t;
int hsh[2];
hsh[0] = hsh[1] = 0;
for(int j = 0 ; j < SZ(t) ; j++)
{
for(int ty = 0 ; ty < 2 ; ty++)
{
hsh[ty] = 1LL * hsh[ty] * Base % mod[ty];
hsh[ty] = modit(ty , hsh[ty] + t[j]);
}
vec.pb({hsh[0] , hsh[1]});
}
}
sort(vec.begin() , vec.end());
vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
string s; cin >> s;
L = SZ(s);
for(int i = 0 ; i < m ; i++) cin >> ar[i].F >> ar[i].S;
prehsh[0][0] = prehsh[1][0] = s[0];
for(int i = 1 ; i < L ; i++) for(int ty = 0 ; ty < 2 ; ty++)
{
prehsh[ty][i] = 1LL * prehsh[ty][i - 1] * Base % mod[ty];
prehsh[ty][i] = modit(ty , prehsh[ty][i] + s[i]);
}
for(int i = 0 ; i < L ; i++)
{
int low = i - 1 , high = L;
while(high - low > 1)
{
int mid = (high + low) >> 1;
auto now = get(i , mid);
int it = lower_bound(vec.begin() , vec.end() , now) - vec.begin();
if(vec[it] == now) low = mid;
else high = mid;
}
rr[i] = high;
}
vector <int> st;
adj[0][L] = {L , L};
rr[L] = L;
st.pb(L);
for(int i = L - 1 ; i > -1 ; i--)
{
if(rr[i] == i)
{
adj[0][i] = {i , i};
st.pb(i);
continue;
}
int low = -1 , high = SZ(st);
while(high - low > 1)
{
int mid = (high + low) >> 1;
if(st[mid] <= rr[i]) high = mid;
else low = mid;
}
adj[0][i] = {st[high] , rr[i]};
while(!st.empty() && rr[i] >= rr[st.back()]) st.pop_back();
st.pb(i);
}
for(int i = 1 ; i < maxl ; i++)
for(int j = 0 ; j <= L ; j++)
adj[i][j] = adj[i - 1][adj[i - 1][j].F];
for(int i = 0 ; i < m ; i++)
cout << solve(ar[i].F , ar[i].S) << '\n';
return 0;
}
