Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem I: 二队-上海-你的名字

Problem I: 二队-上海-你的名字

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 17  Solved: 4
[Submit][Status][Web Board]

Description

任何的字串都可以成为名字的一种,然而并非所有人希望名字和别人相同,在游戏中创建一个虚拟世界时,欣君希望给所有的NPC起一个不同的名字,但是他很懒啊,决定从随便写的字符串中随机截取一段作为NPC的名字,现在有一个很长的字符串,欣君每次想知道在一个随便选取的子串中能截取出多少个不同的名字。

Input

第一行是数据的组数

接下来每组数据首行为这个字符串

接下来一行是询问的数量Q

每个询问包括两个数字l,r表示查询l到r区间的子串中能截取的不同名字数量

1<=|S|<=2000

1<=Q<=10000

Output

每个询问一行输出,表示该询问的答案

Sample Input

1
phqghumeaylnlfdxfirc
10
5 12
3 14
3 13
2 17
16 19
7 8
12 19
10 13
8 20
15 16

Sample Output

36
77
65
133
10
3
35
9
89
3

HINT

[Submit][Status][Web Board]