/*

字符串长度较小， 可以离线或者直接与处理所有区间的答案

动态加入点的时候， 因为对于其他点的parent构造要么没有影响， 要么就是在两个节点之间塞入一个点， 对于minmax的贡献没有改变

所以只统计这个点的贡献就好了

*/

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<queue>

#define ll long long

#define M 4040

#define mmp make_pair

using namespace std;

int read()

{

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int len[M], fa[M], ch[M][26], lst, cnt;

int ans[2020][2020];

char s[M];

void init()

{

	memset(len, 0, sizeof(len));

	memset(ch, 0, sizeof(ch));

	memset(fa, 0, sizeof(fa));

	lst = cnt = 1;

}

void insert(int c)

{

	int p = ++cnt, f = lst;

	lst = p;

	len[p] = len[f] + 1;

	while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];

	if(!f) fa[p] = 1;

	else

	{

		int q = ch[f][c];

		if(len[q] == len[f] + 1) fa[p] = q;

		else

		{

			int nq = ++cnt;

			fa[nq] = fa[q];

			memcpy(ch[nq], ch[q], sizeof(ch[nq]));

			len[nq] = len[f] + 1;

			fa[p] = fa[q] = nq;

			while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];

		}

	}

}

int main()

{

	int t = read();

	while(t--)

	{

		//Init();

		scanf("%s", s + 1);

		int n = strlen(s + 1);

		for(int i = 1; i <= n; i++)

		{

			init();

			for(int j = i; j <= n; j++) insert(s[j] - 'a'), ans[i][j] = ans[i][j - 1] + len[lst] - len[fa[lst]];

		}

		int q = read();

		while(q--)

		{

			int l = read(), r = read();

			cout << ans[l][r] << "\n";

		}

	}

	return 0;

}