Problem Statement

When searching a string $S$ from the beginning, the string $S$ is called a good problem if the substring $\verb|good|$ and the substring $\verb|problem|$ are both found, and the position of the first $\verb|good|$ found is before the position of the first $\verb|problem|$ found.
You repeatedly perform the operation of rewriting $1$ character at any position in the string $S$ to one of $\verb|a|$ to $\verb|z|$.
Output the minimum number of operations required to make the string $S$ a good problem.
(Note: this problem may be easier to understand if you have solved the real good problem.)

Input

The $1$st line contains the number of test cases $T$.
$T$ test cases follow. Each test case consists of $1$ line containing the string $S$.

$|S| \geq 11$.
The string $S$ consists only of lowercase letters.
The sum of the lengths of the string $S$ over all test cases does not exceed $1000000 = 10^6$.

Output

Output the answer for each test case.

Sample

3
veryverygoodproblem
goodexcellentproblems
problemgood

0
0
10

2
goodproblem
agdddekproblemsdl

0
2

9
geodaaaproblem
goodproblen
badendlessprobrem
podpdpprrobleem
problemgoodprobremgood
smallproblem
proproprefurohobbyhobby
gooeproblemd
itisproblemcoolgoodproblem

1
1
4
5
2
4
8
1
1