CF2125F Timofey and Docker

Not 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.

Each 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} $ .

For 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.

Let'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.