U526666 提出好问题(加强版)

本题与[U502600 提出好问题(简单版)](https://www.luogu.com.cn/problem/U502600)背景及要求完全一致，区别在于数据范围和时间限制。 小L在打完了很多比赛后，总结出考高分的方法就是要尽可能多地提出一些好问题（假的）。 小L决定提出问题，但是小L提出的问题不一定是好问题，为了学习尽可能多的知识点，需要使它变成好问题，请你帮助他！ $\large\color{orange}\text{注意：由于小L马上就要考试了，时间非常紧迫，他最多只能等75ms。}$ $\tiny\color{white}\sout{\text{不要问我为什么只有这么点时间 }\text。}$ 时间见表格

小L发现，对于一个字符串 S，如果有子串 "good" 和子串 "problem"，并且第一个 "good" 的位置在第一个 "problem" 的位置前，那么称 S 是好问题串，值得学习。 给定字符串 ，你可以一次操作将任意某个字符替换成 "a" 到 "z" 之间的任何一个字符，问至少多少次操作后， 会变成好问题串。

第一行，一个整数 $T$ 表示测试数据的组数。 后续 $T$ 行，每行一个小写字母组成的字符串 $S$。

输出 $T$ 行，每行一个整数，表示答案，$\Large\color{red}\text{注意时间上的限制!}$

**数据规模与约定** | 测试组序号 | 编号及数据性质 | 对应分值 | 最大时间 | | -----------: | -----------: | -----------: | -----------: | | Subtask #0 | 1-1,有性质A与B | 0x1=0.0 | 20.0ms | | Subtask #1 | 7,8,9,满足性质B | 3x10=30 | 50.0ms | | Subtask #2 | 2-6,10,11,性质B | 7x10=70 | 75.0ms | 性质A：满足与样例$[1,4]$输入与输出完全相同(测试用) 性质B：$S$ 的长度至少是 $11$，所有测试数据的 $S$ 的长度之和不超过 $1000000$。 **注意时间上的限制。** **提示** 本题不需要算法 若实在没有思路，请参考[题解](https://www.luogu.com.cn/article/2kvvw06w)做法。 若文章无法查看，请下载附件中的txt文件，将其全选复制至[云剪贴板](https://www.luogu.com.cn/paste)查看。