# 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".


wange2014

## Source

2015 ACM/ICPC Asia Regional Shenyang Online