#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define PB push_back
#define ll long long
#define ld long double
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0);
const ll maxn = 3e5 + 4 , N = 1e4 + 4 , base = 107 , mod = 1e9 + 7 , INF = 1e9;
ll pbase[maxn];
int n , m , SZ , res[maxn] , dp[maxn] , pos[maxn] , seg[4 * maxn];
string t[N];
vector <ll> h[N];
vector <pii> q[maxn];
void pre() {
pbase[0] = 1;
for (int i = 1; i < maxn; ++i) {
pbase[i] = (pbase[i - 1] * base) % mod;
}
for (int i = 0; i <= n; ++i) {
h[i].PB(0);
for (int j = 1; j <= _sz(t[i]); ++j) {
int val = (h[i].back() * base + t[i][j - 1]) % mod;
h[i].PB(val);
}
}
}
inline int HASH(int i , int l , int r) {
return (h[i][r] - (h[i][l] * pbase[r - l] % mod) + mod) % mod;
}
inline int LCP(int x , int i) {
if(t[0][x] != t[i][0]) return 0;
int l = 1 , r = min(SZ - x , _sz(t[i])) + 1;
while(l < r - 1) {
int mm = (l + r) / 2;
if(HASH(0 , x , x + mm) == HASH(i , 0 , mm)) l = mm;
else r = mm;
}
return l;
}
inline bool check(int x , int i) {
int lcp = LCP(x , i);
if(x + lcp == SZ) return (_sz(t[i]) > lcp);
if(_sz(t[i]) == lcp) return 0;
return t[0][x + lcp] < t[i][lcp];
}
inline int bs(int x) {
if(check(x , 1)) return 1;
int l = 1 , r = n + 1;
while(l < r - 1) {
int mm = (l + r) / 2;
if(check(x , mm)) r = mm;
else l = mm;
}
return r;
}
void add(int p , int x , int v = 1 , int s = 0 , int e = SZ) {
seg[v] = min(seg[v] , x);
if(e - s == 1) return ;
if(p < mid) {
add(p , x , lc , s , mid);
return ;
}
add(p , x , rc , mid , e);
}
int get(int l , int r , int v = 1 , int s = 0 , int e = SZ) {
if(l >= e || s >= r) return INF;
if(l <= s && e <= r) return seg[v];
return min(get(l , r , lc , s , mid) , get(l , r , rc , mid , e));
}
int32_t main() {
FAST;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> t[i];
}
cin >> t[0];
sort(t + 1 , t + 1 + n);
for (int i = 0; i < m; ++i) {
int l , r; cin >> l >> r; r--;
q[r].PB({l , i});
}
pre();
SZ = _sz(t[0]);
for (int i = 0; i < SZ; ++i) {
pos[i] = bs(i);
if(_sz(q[i])) {
fill(seg , seg + 4 * SZ , INF);
fill(dp , dp + SZ , INF);
for (int j = i; j >= 0; --j) {
int mx = 0;
if(pos[j] <= n) mx = max(mx , LCP(j , pos[j]));
if(pos[j] > 0) mx = max(mx , LCP(j , pos[j] - 1));
dp[j] = (mx >= i - j + 1 ? 1 : get(j + 1 , j + mx + 1) + 1);
add(j , dp[j]);
}
for (auto x : q[i]) {
res[x.S] = dp[x.F];
}
}
}
for (int i = 0; i < m; ++i) {
cout << (res[i] >= INF ? -1 : res[i]) << '\n';
}
}
