还是分块?

今年3月份校赛的时候，"分块?"一题让许多同学了解了这个算法，小明特别喜欢这个算法，于是想出了一道类似的题目来考考你——

给出字符串，给定一个固定长度L，给出很多个询问，每个询问有两个端点l,r,请你计算区间[l,r]内长度为L的不同子串有多少个。

还是分块吗？聪明的你来挑战一下吧！

输入数据第1行是一个整数T（1 <= T <= 10），表示有T组测试用例。

每个测试用例：
第1行输入一个字符串（由小写字母组成，长度小于10000）；
第2行输入一个数字L，表示固定的长度；
第3行输入询问组数Q（Q <= 10000）；
接下来Q组询问，每个询问包含两个整数l,r(l <= r,且保证小于串长)；

特别提醒：字符串下标从1开始。

对于每组测试用例，输出Q行，回答询问。

1
aabc
1
2
1 2
2 3

1
2

杭电ACM程序设计竞赛（2014’05）(暨暑期集训队选拔赛)