Fang Fang

Time Limit: 1500/1000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Description

Fang Fang says she wants to be remembered.
I promise her. We define the sequence $F$ of strings.
$F_{0}\ =\ ``\texttt{f}",$
$F_{1}\ =\ ``\texttt{ff}",$
$F_{2}\ =\ ``\texttt{cff}",$
$F_{n}\ =\ F_{n-1}\ +\ ``f",\ for\ n\ >\ 2$
Write down a serenade as a lowercase string $S$ in a circle, in a loop that never ends.
Spell the serenade using the minimum number of strings in $F$, or nothing could be done but put her away in cold wilderness.

Input

An positive integer $T$, indicating there are $T$ test cases.
Following are $T$ lines, each line contains an string $S$ as introduced above.
The total length of strings for all test cases would not be larger than $10^6$.

Output

The output contains exactly $T$ lines.
For each test case, if one can not spell the serenade by using the strings in $F$, output $-1$. Otherwise, output the minimum number of strings in $F$ to split $S$ according to aforementioned rules. Repetitive strings should be counted repeatedly.

Sample Input

8 ffcfffcffcff cffcfff cffcff cffcf ffffcffcfff cffcfffcffffcfffff cff cffc

Sample Output

Case #1: 3 Case #2: 2 Case #3: 2 Case #4: -1 Case #5: 2 Case #6: 4 Case #7: 1 Case #8: -1
Hint
Shift the string in the first test case, we will get the string "cffffcfffcff" and it can be split into "cffff", "cfff" and "cff".

Hint

wange2014

Source

2015 ACM/ICPC Asia Regional Shenyang Online

提交代码