#include <stdio.h>
#include <stdlib.h>

typedef struct HList {
	struct HList *next;
	int l, r, min, argmin[2];
} hlist;

#define HASH 5000011
const int H_Mod = HASH;
int hn;
hlist *hash[HASH] = {}, hd[10000001];

int hash_func(int l, int r)
{
	return (((long long)l << 30) + r) % H_Mod;
}

void Z_algorithm(char S[], int Z[])
{
	int i, j, k, l;
	for (l = 0; S[l] != 0; l++);
	Z[0] = l;
	for (i = 1, j = 0; i < l; i++) {
		for (; i + j < l && S[i+j] == S[j]; j++);
		Z[i] = j;
		if (j == 0) continue;
		
		for (k = 1; k < j && k + Z[k] < j; k++) Z[i+k] = Z[k];
		i += k - 1;
		j -= k;
	}
}

int recursion(char S[], int l, int r)
{
	if (r <= l) return 0;
	else if (r == l + 1) return 2;
	
	int h = hash_func(l, r);
	hlist *hp;
	for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->l == l && hp->r == r) return hp->min;
	hp = &(hd[hn++]);
	hp->l = l;
	hp->r = r;
	hp->min = r - l + 1;
	hp->argmin[0] = l;
	hp->argmin[1] = r;
	hp->next = hash[h];
	hash[h] = hp;
	
	int m = (l + r) / 2, tmp[2] = {recursion(S, l, m), recursion(S, m, r)};
	if (hp->min > tmp[0] + tmp[1]) {
		hp->min = tmp[0] + tmp[1];
		hp->argmin[0] = m;
		hp->argmin[1] = m;
	}
	
	int i, j, k, kk, kkk, ll, rr, *Z[2];
	char *T[2];
	T[0] = (char*)malloc(sizeof(char) * (m - l + 1));
	T[1] = (char*)malloc(sizeof(char) * (r - m + 1 + r - l + 1));
	Z[0] = (int*)malloc(sizeof(int) * (m - l + 1 + 1));
	Z[1] = (int*)malloc(sizeof(int) * (r - m + 1 + r - l + 1));
	for (i = 0, j = m - 1; j >= l; i++, j--) T[0][i] = S[j];
	T[0][i] = 0;
	Z[0][i] = 0;
	for (i = 0, j = m; j < r; i++, j++) T[1][i] = S[j];
	T[1][i++] = '#';
	for (j = l; j < r; i++, j++) T[1][i] = S[j];
	T[1][i] = 0;
	Z_algorithm(T[0], Z[0]);
	Z_algorithm(T[1], Z[1]);
	for (i = 1, j = m - l; i <= m - l && j >= 0; i++, j--) {
		k = Z[0][i] + Z[1][r-m+j] + i;
		if (k < i * 2) continue;
		for (kk = k / i, kkk = 0; kk > 0; kk /= 10, kkk++);
		kk = k / i * i;
		for (ll = m - i - Z[0][i], rr = ll + kk; rr <= m + Z[1][r-m+j]; ll++, rr++) {
			if (rr < m) continue;
			tmp[0] = recursion(S, l, ll);
			tmp[1] = recursion(S, rr, r);
			if (hp->min > tmp[0] + tmp[1] + i + kkk) {
				hp->min = tmp[0] + tmp[1] + i + kkk;
				hp->argmin[0] = ll;
				hp->argmin[1] = rr;
			}
		}
	}
	free(T[0]);
	free(T[1]);
	free(Z[0]);
	free(Z[1]);
	
	T[0] = (char*)malloc(sizeof(char) * (r - m + 1));
	T[1] = (char*)malloc(sizeof(char) * (m - l + 1 + r - l + 1));
	Z[0] = (int*)malloc(sizeof(int) * (r - m + 1 + 1));
	Z[1] = (int*)malloc(sizeof(int) * (m - l + 1 + r - l + 1));
	for (i = 0, j = m; j < r; i++, j++) T[0][i] = S[j];
	T[0][i] = 0;
	Z[0][i] = 0;
	for (i = 0, j = m - 1; j >= l; i++, j--) T[1][i] = S[j];
	T[1][i++] = '#';
	for (j = r - 1; j >= l; i++, j--) T[1][i] = S[j];
	T[1][i] = 0;
	Z_algorithm(T[0], Z[0]);
	Z_algorithm(T[1], Z[1]);
	for (i = 1, j = r - m; i <= r - m && j >= 0; i++, j--) {
		k = Z[0][i] + Z[1][m-l+j] + i;
		if (k < i * 2) continue;
		for (kk = k / i, kkk = 0; kk > 0; kk /= 10, kkk++);
		kk = k / i * i;
		for (rr = m + i + Z[0][i], ll = rr - kk; ll >= m - Z[1][m-l+j]; ll--, rr--) {
			if (ll > m) continue;
			tmp[0] = recursion(S, l, ll);
			tmp[1] = recursion(S, rr, r);
			if (hp->min > tmp[0] + tmp[1] + i + kkk) {
				hp->min = tmp[0] + tmp[1] + i + kkk;
				hp->argmin[0] = ll;
				hp->argmin[1] = rr;
			}
		}
	}
	free(T[0]);
	free(T[1]);
	free(Z[0]);
	free(Z[1]);
	// printf("%d %d: %d %d %d\n", l, r, hp->min, hp->argmin[0], hp->argmin[1]);
	return hp->min;
}

void recover(char S[], int l, int r, char ans[])
{
	if (r <= l) return;
	else if (r == l + 1) {
		ans[0] = S[l];
		ans[1] = '1';
		return;
	}
	
	int h = hash_func(l, r), i, j, k = 0, kk;
	char tmp[10];
	hlist *hp;
	for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->l == l && hp->r == r) break;
	if (hp->argmin[0] > l) {
		recover(S, l, hp->argmin[0], ans);
		k = recursion(S, l, hp->argmin[0]);
	}
	if (hp->argmin[0] < hp->argmin[1]) {
		for (i = 1; i < hp->argmin[1] - hp->argmin[0]; i++) {
			if ((hp->argmin[1] - hp->argmin[0]) % i != 0) continue;
			for (j = hp->argmin[0] + i; j < hp->argmin[1]; j++) if (S[j] != S[j-i]) break;
			if (j == hp->argmin[1]) break;
		}
		for (j = 0; j < i; j++) ans[k++] = S[hp->argmin[0] + j];
		for (j = (hp->argmin[1] - hp->argmin[0]) / i, kk = 0; j > 0; j /= 10, kk++) tmp[kk] = '0' + j % 10;
		while (kk--) ans[k++] = tmp[kk];
	}
	if (hp->argmin[1] < r) recover(S, hp->argmin[1], r, &(ans[k]));
}

void solve(char S[], char ans[])
{
	int h, i, l, min;
	for (l = 0, hn = 0; S[l] != 0; l++);
	min = recursion(S, 0, l);
	recover(S, 0, l, ans);
	ans[min] = 0;
	for (i = 0; i < hn; i++) hash[hash_func(hd[i].l, hd[i].r)] = NULL;
}

int main()
{
	int T;
	char S[500001], ans[500003];
	scanf("%d", &T);
	while (T--) {
		scanf("%s", S);
		solve(S, ans);
		printf("%s\n", ans);
	}
	fflush(stdout);
	return 0;
}