#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int T, ans;
int a[15];// ,g,o,d,m,r,n,i
char c;
int main() {
    scanf("%d", &T);
    c = getchar();
    while (c != '\n')getchar();
    for (int i = 1; i <= T; i++) {
        memset(a, 0, sizeof(a));
        ans = 0x3f3f3f3f;
        c = getchar();
        while (c != '\n') {
            if (c == ' ')a[0]++;
            else if (c == 'g')a[1]++;
            else if (c == 'o')a[2]++;
            else if (c == 'd')a[3]++;
            else if (c == 'm')a[4]++;
            else if (c == 'r')a[5]++;
            else if (c == 'n')a[6]++;
            else if (c == 'i')a[7]++;
            c = getchar();
        }
        ans = min(a[0] / 1, min(a[1] / 2, min(a[2] / 3, min(a[3] / 1, min(a[4] / 1, min(a[5] / 1, min(a[6] / 2, a[7] / 1)))))));
        printf("Case #%d: %d\n", i, ans);
    }
}