#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F
const int MXN = 3e5 + 5;
const int mod = 1e9 + 7;
int b1, b2;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dp[505][505];
int R[505];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 505; i++) for (int j = 0; j < 505; j++) dp[i][j] = -1;
int k, m;
cin >> k >> m;
string t[k];
for (int i = 0; i < k; i++) cin >> t[i];
string s;
cin >> s;
int n = s.length();
s = "#" + s;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < k; j++)
{
for (int l = i; l <= n; l++)
{
if (s[l] != t[j][l - i]) break;
R[i] = max(R[i], l);
}
}
}
for (int sz = 1; sz <= n; sz++)
{
for (int i = 1; i + sz - 1 <= n; i++)
{
int j = i + sz - 1;
if (R[i] >= j) dp[i][j] = 1;
else dp[i][j] = inf;
for (int k = i; k < j; k++)
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
for (int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
l++;
cout << (dp[l][r] == inf ? -1 : dp[l][r]) << '\n';
}
}
