#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
int t, sum[27][1500005], cnt;
unsigned long long ha[1500005], p[1500005];
char s[1500005];
int main() {
    scanf("%d", &t);
    while(t--) {
    	scanf("%s", s+1);
    	int len = strlen(s+1);
    	p[0] = 1;
    	for(int i = 1;s[i];++i) {
    		sum[s[i]-'a'+1][i] = sum[s[i]-'a'+1][i-1] + 1;
    		ha[i] = ha[i-1] * 131 + (s[i]-'a'+1);
    		p[i] = p[i-1] * 131;
    	}
    	for(int i = 1;s[i];++i) {
    		int dif1 = 0;
    		for(int j = 1;j <= 26;++j)
    			if((sum[j][i]-sum[j][0]) % 2 == 1) ++dif1;
    		for(int j = i+1;s[j];++j) {
    			ull x = ha[j] - ha[0]*p[j];
    			for(int k = 1;k*j<len && ha[k*j]-ha[(k-1)*j]*p[j] == x;++k) {
    				int st = k*j + 1, dif2 = 0;
    				for(int l = 1;l <= 26;++l)
    					if((sum[l][len]-sum[l][st-1])%2 == 1) ++dif2;
    				if(dif1 <= dif2) {
    					//for(int m = 1;m <= i;++m) putchar(s[m]);
    					//printf(" ");
    					//for(int m = i+1;m <= st-1;++m) putchar(s[m]);
    					//printf(" ");
    					//for(int m = st;m <= len;++m) putchar(s[m]);
    					printf(" \n");
                 ++cnt;
    				}
    			}
    		}
    	}
    	printf("%d\n", cnt);
    }
    return 0;
}