2015
09-17

# Hehe

As we all know, Fat Brother likes MeiZi every much, he always find some topic to talk with her. But as Fat Brother is so low profile that no one knows he is a rich-two-generation expect the author, MeiZi always rejects him by typing “hehe” (wqnmlgb). You have to believe that there is still some idealized person just like Fat Brother. They think that the meaning of “hehe” is just “hehe”, such like “hihi”, “haha” and so on. But indeed sometimes “hehe” may really means “hehe”. Now you are given a sentence, every “hehe” in this sentence can replace by “wqnmlgb” or just “hehe”, please calculate that how many different meaning of this sentence may be. Note that “wqnmlgb” means “我去年买了个表” in Chinese.

The first line contains only one integer T, which is the number of test cases.Each test case contains a string means the given sentence. Note that the given sentence just consists of lowercase letters.
T<=100
The length of each sentence <= 10086

The first line contains only one integer T, which is the number of test cases.Each test case contains a string means the given sentence. Note that the given sentence just consists of lowercase letters.
T<=100
The length of each sentence <= 10086

4
wanshangniyoukongme
womenyiqichuqukanxingxingba
bulehehewohaiyoushi
eheheheh

Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 3

//dp，但是找规律也可以发现连续的是FIb数列.
#include <iostream>
#include <cstring>
using namespace std;

long long tar[10100];

void create_fib()
{
tar[0]=1;
tar[1]=1;
for(int i=2;i<=10086;i++)
{
tar[i]=tar[i-1]+tar[i-2];
tar[i]%=10007;
}
}

int main()
{
int testcase;
string str;
create_fib();
cin>>testcase;
for(int t=1;t<=testcase;t++)
{
cin>>str;
for(int i=0;i<str.length();)
{
if(str[i]=='h' && str[i+1]=='e')
{
count++;
i+=2;
}
else
{
count=0;
i++;
}
}