Jay and Kay decide to play a game. They write an English sentence on a piece of paper. The objective of the game is to pick out some of the written alphabets, rearrange them, and form the longest "lovely string".

The definitions of "lovely string" are simple:

1. It consists of upper case alphabets only, and it cannot be an empty string;
2. All alphabets are assigned a value. For example, A is assigned to be 1, B is assigned to be 2...etc;
3. For any substring of two alphabets, suppose the value of the first alphabet is V₁ and that of the second alphabet is V₂. Then the following inequality must hold: 5 × V₁ ≤ 4 × V₂.

Jay asks you to help him. However, as he does not want to lose the fun of the game, he asks you to give him a hint only. Write a program to give the hint.

Input

The input contains an integer N (1 ≤ N ≤ 30). Each of the next N lines consists of a string S. The string can be as long as 250 characters, and will not contain lower case alphabets.

Output

For each case, print the length of the longest lovely string that can be formed using the alphabets, followed by the number of ways to achieve this length.

Sample Input

2
HELLO.
I AM JAY.

Sample Output

4 1
4 2

Explanation

For the first case, we can get the lovely string EHLO.
For the second case, we can get AIMY and AJMY.

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    char cmd[300];
    int dp[300], way[300];
    gets(cmd);
    while(gets(cmd)) {
        int cnt[26] = {}, i, j;
        for(i = 0; cmd[i]; i++) {
            if(cmd[i] >= 'A' && cmd[i] <= 'Z')
                cnt[cmd[i]-'A']++;
        }
        for(i = 0, j = 0; i < 26; i++)
            if(cnt[i])
            cmd[j++] = i+1;
        int n = j;
        int mx = 0, mxway;
        for(i = 0; i < n; i++) {
            dp[i] = 1, way[i] = 0;
            for(j = 0; j < i; j++)
                if(cmd[j]*5 <= cmd[i]*4)
                    dp[i] = max(dp[i], dp[j]+1);
            for(j = 0; j < i; j++)
                if(cmd[j]*5 <= cmd[i]*4 && dp[i] == dp[j]+1)
                    way[i] += way[j];
            if(dp[i] == 1)  way[i] = 1;
            if(dp[i] > mx)  mx = dp[i], mxway = 0;
            if(dp[i] == mx) mxway += way[i];
        }
        printf("%d %d\n", mx, mxway);
    }
    return 0;
}