Migrated from Lutece 486 Good Morning

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Sam loves Lily very much that he shows his love to her through all kinds of ways. This morning, Lily received an e-mail from Sam. Lily knows that Sam hided "good morning" in this mail. Lily tried several ways to resort the letters (including the space ' ') so that more "good morning"s could be found. The number of "good morning" appeared in a specified string equals the number of positions from which Lily could see a consecutive string "good morning".

With so many letters, Lily is about to be dizzy. She asks you to tell her what is the maximum number of "good morning"s appear in this mail after rearranged in some way.

Input

First an integer $T$ ($T \leq 20$), indicates there are $T$ test cases.

Every test case begins with a single line consist of only lowercase letters and space which is at most $1000$ characters.

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and starts at $1$. Then output an integer indicating the answer to this test case.

Samples

2
gninrom doog
ggoooodd  mmoorrnniinngg

Case #1: 1
Case #2: 2

Resources

Sichuan State Programming Contest 2011