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.

Input

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

Output

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.

Note

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.

Idx	Name	Rating
A	Difficult Contest	800
B	Left and Down	900
C	Count Good Numbers	1100
D	Segments Covering	1600
E	Sets of Complementary Sums	2500
F	Timofey and Docker	3000

Educational Codeforces Round 181 (Rated for Div. 2)