记录编号	167981	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]串	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.782 s
提交时间	2015-06-30 09:43:50	内存使用	19.37 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
//#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 10000100
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 10000002;

char S[maxn << 1];
int N;

inline void init(){
	int ch;N = 0;
	while(!isalpha(ch = getc()));S[N++] = ch;
	while(isalpha(ch = getc()))S[N++] = ch;
}

inline int GetMin(int len){
	int i = 0, j = 1, k;
	while(j < len){
		if(S[i] < S[j])++j;
		else if(S[i] > S[j])i = j++;
		else{
			k = 1;
			while(k < len && S[i+k] == S[j+k])++k;
			if(S[i+k] > S[j+k])i += k + 1;
			else j += k + 1;
			if(i == j)++j;
		}
	}
	return i;
}

inline void work(){
	int i, j;
	for(i = 0, j = N-1;i < j;++i, --j)swap(S[i], S[j]);
	for(i = 0;i < N;++i)S[i + N] = S[i];
	i = GetMin(N);
	j = GetMin(i);
	printf("%d %d\n", N - i, N - j);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(nt2012_rev);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif
	int T;getd(T);
	while(T--){
		init();
		work();
	}

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}