F. Timofey 与 Docker
时间限制：2 秒
内存限制：512 兆字节

不久前，某个叫 Timofey 的人了解了 Docker，现在想在一个会议上做关于它的报告。他已经准备好了讲稿 $s$。

会议有 $n$ 个人参加。第 $i$ 个人能理解 Timofey 的报告，当且仅当讲稿中单词 "docker" 作为连续子串出现的次数 $\ge l_i$ 且 $\le 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$ 中的某些字符改为 "ldockerkdocker"，这样会有 $3$ 个人理解，这是最大值。