F. Timofey and Dockertime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputNot so long ago, a certain Timofey learned about docker and now wants to present a report about it at a conference. He has already prepared the text $$$s$$$.There are $$$n$$$ people attending the conference. The $$$i$$$-th attendee will understand Timofey's report if the number of occurrences of the word "docker" as a contiguous substring in the text is not less than $$$l_i$$$ and not greater than $$$r_i$$$.To ensure that as many people as possible learn about docker, Timofey can change characters in his text.Help Timofey determine the minimum number of characters that need to be changed so that the topic is understood by the maximum possible number of attendees.InputEach test consists of several test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains one string $$$s$$$ ($$$1 \le |s| \le 5 \cdot 10^{5}$$$) — Timofey's text, which consists of lowercase Latin letters.The second line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — the number of attendees.The next $$$n$$$ lines of each test case contain two integers $$$l_{i}, r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le 10^{9}$$$).Additional constraints on the input data: The sum of $$$|s|$$$ across all test cases does not exceed $$$5 \cdot 10^{5}$$$; The sum of $$$n$$$ across all test cases does not exceed $$$5 \cdot 10^{5}$$$. OutputFor each test case, print one integer — the minimum number of characters that need to be changed so that the topic is understood by the maximum number of attendees.ExamplesInput2dockerdockerxxxxxx33 32 41 5ljglsjfkdieufj51 53 32 43 72 9Output6
11
Input4dockerdockerdockerdockzzdockzz41 11 14 54 5docker51 12 23 34 45 5ddddddoooooocccccckkkkkkeeeeeerrrrrr101 200500 6001 6006 66 6500 20006 40089 904 71 10dockerdockerdockerdockzzdockzz42 22 24 54 5Output2
0
30
1
NoteLet's consider the first test in more detail: in the first test case, it is possible to change all the characters '$$$x$$$' at the end of the string to the whole word "$$$docker$$$", so that all $$$3$$$ people will understand the topic; in the second test case, it is possible to change some characters in $$$s$$$ as follows: "$$$l\color{red}{docker}kd\color{red}{ocker}$$$" and the topic will be understood by $$$3$$$ people, which is the maximum.