F. Тимофей и докер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Совсем недавно некий Тимофей узнал про докер и теперь хочет выступить с докладом о нем на конференции. У него уже подготовлен текст доклада $$$s$$$.

Доклад Тимофея будут слушать $$$n$$$ людей; $$$i$$$-й слушатель поймет тему в том случае, если количество вхождений слова «docker» как непрерывной подстроки в текст будет не меньше $$$l_i$$$ и не больше $$$r_i$$$.

Чтобы как можно больше людей узнали про докер, Тимофей может изменять символы в своем тексте.

Помогите Тимофею узнать минимальное количество символов, которые надо изменить, чтобы тему поняло максимальное количество слушателей.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит строку $$$s$$$ ($$$1 \le |s| \le 5 \cdot 10^{5}$$$) — текст Тимофея, который состоит из строчных букв латинского алфавита.

Вторая строка каждого набора входных данных содержит одно целое число $$$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$$$ так: «$$$l\color{red}{docker}kd\color{red}{ocker}$$$» и тему поймут $$$3$$$ человека, что является максимумом.