Extra爱打CF

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
7.14%(1/14)
Description:

Extra平时很无聊,喜欢打CF,不过他的CF技术嘛蛮(挺)6(坑)的。他的数学还蛮厉害的(真的!!),
并且他希望CF可以永远被大家记住,所以他设计出了CF字符串组:
CF0="F"
CF1="FF"
CF2="CFF"
CFn=CFn-1+"F",(n>=3);
现在他就想知道茫茫字符串海中的CF字符串的最少个数(TIP:求字符串中最少的CF字符串个数)。
当然对于数学大神Extra来说,CF是没有起点也没有终点的,所以对于他来说其实是一个圈

Input:

第一行输入整数T(T<=20)
接下来T行,每行有一个字符串,长度不超过1000000

Output:

输出T行。每个字符串输出一行,输出一个整数x,代表该字符串里面所含有的CF字符串组中的元素个数,如果字符串中存在不可以从CF字符串组中,则输出-1

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:

CFFCFFFCFFFF中含有“CFF”,”CFFF”,”CFFFF”,所以是3个


Submit