Fang Fang

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 685 Accepted Submission(s): 285

Problem Description

Fang Fang says she wants to be remembered.

I promise her. We define the sequence

F of strings.

F0 = ‘‘f",

F1 = ‘‘ff",

F2 = ‘‘cff",

Fn = Fn−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

106 .

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

8ffcfffcffcffcffcfffcffcffcffcfffffcffcfffcffcfffcffffcfffffcffcffc

Sample Output

Case #1: 3Case #2: 2Case #3: 2Case #4: -1Case #5: 2Case #6: 4Case #7: 1Case #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".

Source

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=1e6+10;char s[N];int main(){    int t,now,i,re,c,f;    bool ok,oc;    scanf("%d",&t);    for(now=1;now<=t;now++){        scanf("%s",s);        re=0;        ok=1;        oc=0;        f=0;        for(i=0;s[i]!='\0';i++){            if(s[i]=='c'){                       c=0;                i++;                oc=1;                 while(s[i]=='f'){                    c++;i++;                }                if(s[i]=='\0'){                   if(c+f<2){                       ok=0;                       break;                   }                }                else if(s[i]=='c'){                    if(c<2){                    ok=0;                        break;                    }                }                else{                    ok=0;                break;                }                re++;                i--;            }            else if(s[i]=='f')               f++;            else{                ok=0;                break;            }            }            if(!ok)          printf("Case #%d: -1\n",now);        else if(!oc)          printf("Case #%d: %d\n",now,f/2+f%2);              else if(ok)           printf("Case #%d: %d\n",now,re);    }    return 0;}