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.

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

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.

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.

提交代码