#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 2007;
int sz, last;
struct Node
{
    int son[26];
    int father;
    int len;
} t[N << 1];
void newNode(int length)
{
    t[++sz].len = length;
    t[sz].father = -1;
    memset(t[sz].son, 0, sizeof(t[sz].son));
}
void init()
{
    sz = -1;
    last = 0;
    newNode(0);
}
void Insert(int c)
{
    newNode(t[last].len + 1);
    int p = last, cur = sz;
    while (p != -1 && !t[p].son[c])
        t[p].son[c] = cur, p = t[p].father;
    if (p == -1)
        t[cur].father = 0;
    else
    {
        int q = t[p].son[c];
        if (t[q].len == t[p].len + 1)
            t[cur].father = q;
        else
        {
            newNode(t[p].len + 1);
            int nq = sz;
            memcpy(t[nq].son, t[q].son, sizeof(t[q].son));
            t[nq].father = t[q].father;
            t[cur].father = t[q].father = nq;
            while (p >= 0 && t[p].son[c] == q)
                t[p].son[c] = nq, p = t[p].father;
        }
    }
    last = cur;
}
char S[N];
int ans[N][N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", S);
        int n = strlen(S);
        for (int i = 0; i < n; i++)
        {
            init();
            for (int j = i; j < n; j++)
            {
                Insert(S[j] - 'a');
                ans[i][j] = ans[i][j - 1] + t[last].len - t[t[last].father].len;
            }
        }
        int q, l, r;
        scanf("%d", &q);
        while (q--)
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", ans[--l][--r]);
        }
    }
    return 0;
}