Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 131072/65536 K (Java/Others)

Now you are back,and have a task to do:

Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s.

And you have some query,each time you should calculate f(s[l...r]), s[l...r] means the sub-string of s start from l end at r.

Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s.

And you have some query,each time you should calculate f(s[l...r]), s[l...r] means the sub-string of s start from l end at r.

The first line contains integer T(1<=T<=5), denote the number of the test cases.

For each test cases,the first line contains a string s(1 <= length of s <= 2000).

Denote the length of s by n.

The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.

Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.

For each test cases,the first line contains a string s(1 <= length of s <= 2000).

Denote the length of s by n.

The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.

Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.

提交代码