#ifdef __INFOARENA_PROJ
#include "infoarena.h"
#endif

#include <fstream>
#include <algorithm>

#ifdef __INFOARENA_PROJ
namespace prefix {
#endif

unsigned const int maxL = 1000000;
char s[maxL + 2];
unsigned pref[maxL + 1];

void buildPrefixTable(const char* W, unsigned* T)
{
	T[1] = 0;
	unsigned q = 0, pos = 2;
	while (W[pos] != '\0')
	{
		if (W[pos - 1] == W[q])
			T[pos++] = ++q;
		else if (q == 0)
			T[pos++] = 0;
		else while (q > 0)
			q = T[q];
	}
}

unsigned periodicPrefixLength(unsigned start, unsigned len)
{
	if ((start + len) / start > 1)
		return ((start + len) / start) * start;

	return 0;
}

int main()
{
	std::ifstream in("prefix.in");
	std::ofstream out("prefix.out");
	unsigned T;
	in >> T;
	in.getline(s, maxL + 1);
	for (unsigned i = 1; i <= T; ++i)
	{
		in.getline(s, maxL + 1);
		unsigned len = (unsigned) in.gcount() - 1;
		if (s[len] != '\0') ++len;
		s[len] = '*';
		s[len + 1] = '\0';
		++len;

		buildPrefixTable(s, pref);
		unsigned (&localPref)[maxL] = (unsigned(&)[maxL])(*(pref + 1));
		char (&localS)[maxL + 2] = s;
		unsigned seqStart = 1, seqLen = 0, maxLen = 0;
		for (unsigned j = 1; j <= len; ++j)
		{
			if (localPref[j] == localPref[j - 1] + 1)
				++seqLen;
			else maxLen = std::max(maxLen, periodicPrefixLength(seqStart, seqLen));
			if (localPref[j] == 1)
				seqStart = j, seqLen = 1;
		}

		out << maxLen << '\n';
	}
	return 0;
}

#ifdef __INFOARENA_PROJ
}
#endif