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