← 返回题目列表

Codeforces · 2125/F

F. 蒂莫菲和 Docker

中文机器翻译题面 查看原题

不久前,某 Timofey 了解了 docker,现在想在会议上做一个关于 docker 的报告。他已经准备好了文本$$$s$$$。

有 $$$n$$$ 人参加会议。如果单词“出现的次数”,第 $$$i$$$ 位与会者将理解 Timofey 的报告码头工人" 作为文本中的连续子字符串不小于 $$$l_i$$$ 且不大于 $$$r_i$$$。

为了确保尽可能多的人了解 docker,Timofey 可以更改文本中的字符。

帮助 Timofey 确定需要更改的最少字符数,以便尽可能多的与会者能够理解该主题。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 5 \cdot 10^{5}$$$) - Timofey 的文本,由小写拉丁字母组成。

每个测试用例的第二行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — 与会者人数。

每个测试用例接下来的 $$$n$$$ 行包含两个整数 $$$l_{i}, r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le 10^{9}$$$)。

输入数据的附加约束:

  • 所有测试用例的 $$$|s|$$$ 总和不超过 $$$5 \cdot 10^{5}$$$;
  • 所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印一个整数 — 需要更改的最少字符数,以便最大数量的与会者能够理解该主题。

示例

输入
复制

2
dockerdockerxxxxxx
3
3 3
2 4
1 5
ljglsjfkdieufj
5
1 5
3 3
2 4
3 7
2 9

输出
复制

6
11

输入
复制

4
dockerdockerdockerdockzzdockzz
4
1 1
1 1
4 5
4 5
docker
5
1 1
2 2
3 3
4 4
5 5
ddddddoooooocccccckkkkkkeeeeeerrrrrr
10
1 200
500 600
1 600
6 6
6 6
500 2000
6 400
89 90
4 7
1 10
dockerdockerdockerdockzzdockzz
4
2 2
2 2
4 5
4 5

输出
复制

2
0
30
1

注意

让我们更详细地考虑第一个测试:

  • 在第一个测试用例中,可以将字符串末尾的所有字符'$$$x$$$'更改为整个单词“$$$docker$$$”,这样所有$$$3$$$的人都会理解该主题;
  • 在第二个测试用例中,可以将$$$s$$$中的一些字符更改为:“$$$l\color{red}{docker}kd\color{red}{ocker}$$$”,并且该主题将被$$$3$$$人理解,这是最多的。