Problem 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.

8
ffcfffcffcff
cffcfff
cffcff
cffcf
ffffcffcfff
cffcfffcffffcfffff
cff
cffc

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