不久前,某 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}$$$。
输出
对于每个测试用例,打印一个整数 — 需要更改的最少字符数,以便最大数量的与会者能够理解该主题。
示例
输入复制
2dockerdockerxxxxxx33 32 41 5ljglsjfkdieufj51 53 32 43 72 9
输出复制
6 11
输入复制
4dockerdockerdockerdockzzdockzz41 11 14 54 5docker51 12 23 34 45 5ddddddoooooocccccckkkkkkeeeeeerrrrrr101 200500 6001 6006 66 6500 20006 40089 904 71 10dockerdockerdockerdockzzdockzz42 22 24 54 5
输出复制
2 0 30 1
注意
让我们更详细地考虑第一个测试:
- 在第一个测试用例中,可以将字符串末尾的所有字符'$$$x$$$'更改为整个单词“$$$docker$$$”,这样所有$$$3$$$的人都会理解该主题;
- 在第二个测试用例中,可以将$$$s$$$中的一些字符更改为:“$$$l\color{red}{docker}kd\color{red}{ocker}$$$”,并且该主题将被$$$3$$$人理解,这是最多的。