The Grinch is back! This year, the Grinch tampered with the Whos' Christmas carol lyrics. In random parts of the lyrics, he has inserted some variation of the word green. A variation that the Grinch may add must start with gr, contain some positive number of e, and end with n.

Help the Whos save Christmas by removing the minimum number of letters from the given words such that no variation of green remains. The lyrics may contain the letters g, r, e, and n, but there cannot exist any substring that is a variation of the word green.

Image: The Grinch (2018)

Input Specification

The first line contains the integer \(N (1 \le N \le 200)\), the number of lyrics.
Each of the next \(N\) lines contains a single word containing only lowercase letters. The length of each word is between \(1\) and \(5000\) (inclusive).

For \(2/10\) of the subtasks, the only variation that appears is gren.
For \(3/10\) of the subtasks, a variation will appear at most once.

Output Specification

For each of the \(N\) words, output the minimum characters that need to be removed.

Sample Input 1

3
chocolatgren
gingreeeeeeebreadgren
ggrenniftgren

Sample Output 1

1
1
2

For chocolatgren we can remove the last n.
For gingreeeeeeebreadgren we can remove the last n.
For ggrenniftgren we can remove the two r.