#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<cmath>

#include<set>

#include<vector>

#include<list>

using namespace std;

typedef long long ll;

typedef pair<double,double>ppd;

const double PI = acos(-1.);

const double eps = (1e-9);

const int MOD=10007;

const int N=5005;

char s[N];

int sum[N];

int main()

{

    //freopen("data.in","r",stdin);

    sum[0]=sum[1]=1;

    sum[2]=2;sum[3]=3;

    for(int i=4;i<N;++i)

    sum[i]=(sum[i-3]+sum[i-2]*2)%MOD;

    int T;

    scanf("%d",&T);

    for(int c=1;c<=T;++c)

    {

        scanf("%s",s);

        int n=strlen(s);

        int ans=1;

        int num=0;

        for(int i=0;i<n;++i)

        {

            if(i+1<n&&s[i]=='h'&&s[i+1]=='e')

            {++num;++i;}

            else

            {

                if(num>=2)

                ans=(ans*sum[num])%MOD;

                num=0;

            }

        }

        if(num>=2)

        ans=(ans*sum[num])%MOD;

        printf("Case %d: %d\n",c,ans);

    }

    return 0;

}