描述

每天早上, doc都会给学姐发一条短信, 里面由小写字母和空格组成.
其实doc只是想和学姐说: "good morning".
如果把doc发给学姐的短信以某种方式重新排序,
就可以得到很多 "good morning"了.
学姐每天都想知道, doc发的短信中究竟能组成多少句"good morning".
举个例子来说, 对于"ggooood  dmmoorrnniinngg",可以组成两个"good morning".
但是对于"goodmorning"来说, 却只能组成0个, 因为里面缺少了空格.
而对于"goodgood morningmorning"来说, 只能组成1个.
如果学姐不能知道答案, 她一整天都会不开心的!

格式

输入格式

输入数据第一行给定T, 表示总的询问次数.
对于每一次询问, 单独一行给出一个由小写字母和空格组成的字符串.

输出格式

对于每一次询问, 首先输出询问的编号, 参见样例输出.
之后输出最多能组成多少句 "good morning"(注意, 里面有一个空格)

样例1

样例输入1

1 
gninrom doog

样例输出1

Case #1: 1

限制

对于50%的数据: 字符串长度<= 30.
对于100%的数据: 字符串长度<= 1000, T <= 20.