#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <stack>#include <string>#include <map>#include <time.h>#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define EPS 1e-6#define FOR0(i,x) for(i=0;i<x;i++)#define FOR1(i,x) for(i=1;i<=x;i++)#define FOR(i,a,b) for(i=a;i<=b;i++)#define FORL0(i,a) for(i=a;i>=0;i--)#define FORL1(i,a) for(i=a;i>=1;i--)#define FORL(i,a,b)for(i=a;i>=b;i--)#define rush() int CC;for(scanf("%d",&CC);CC--;)#define Rush(n) while(scanf("%d",&n)!=-1)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%lld",&x);}void RD(u64 &x){scanf("%I64u",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%lld%lld",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%lld%lld%lld",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%dn",x);}void PR(int x,int y) {printf("%d %dn",x,y);}void PR(i64 x) {printf("%lldn",x);}void PR(i64 x,i64 y) {printf("%lld %lldn",x,y);}void PR(u32 x) {printf("%un",x);}void PR(u64 x) {printf("%llun",x);}void PR(double x) {printf("%.6lfn",x);}void PR(double x,double y) {printf("%.5lf %.5lfn",x,y);}void PR(char x) {printf("%cn",x);}void PR(char *x) {printf("%sn",x);}void PR(string x) {cout<<x<<endl;}const int mod=100000007;const i64 inf=((i64)1)<<40;const double dinf=1000000000000000000.0;const int INF=100000000;const int N=100005;int r[N],sa[N],wa[N],wb[N],wd[N],rank[N],h[N];void da(int *r,int *sa,int n,int m){ int i,j,p,*x=wa,*y=wb,*t; FOR0(i,m) wd[i]=0; FOR0(i,n) wd[x[i]=r[i]]++; FOR1(i,m-1) wd[i]+=wd[i-1]; FORL0(i,n-1) sa[--wd[x[i]]]=i; for(j=1;j<=n;j<<=1) { p=0; for(i=n-j;i<n;i++) y[p++]=i; FOR0(i,n) if(sa[i]>=j) y[p++]=sa[i]-j; FOR0(i,m) wd[i]=0; FOR0(i,n) wd[x[y[i]]]++; FOR1(i,m-1) wd[i]+=wd[i-1]; FORL0(i,n-1) sa[--wd[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; FOR1(i,n-1) { if(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]) { x[sa[i]]=p-1; } else x[sa[i]]=p++; } if(p>=n) return; m=p; }}void calHeight(int *r,int *sa,int n){ int i,j,k=0; FOR1(i,n) rank[sa[i]]=i; FOR0(i,n) { if(k) k--; j=sa[rank[i]-1]; while(i+k<n&&j+k<n&&r[i+k]==r[j+k]) k++; h[rank[i]]=k; }}char s[N];int n,L,pos;int ok(int x){ pos=-1; int i,j,k,t,l,r,flag=0; for(i=1;i<=L;i++) { l=i; while(l<=L&&h[l]<x) l++; if(l>L) break; r=l; while(r<=L&&h[r]>=x) r++; i=r; if(r-l+1<n) continue; flag=1; k=0; for(j=l-1;j<r;j++) { k=max(k,sa[j]); } if(k>pos) pos=k; } return flag;}int main(){ Rush(n) { if(!n) break; RD(s); L=strlen(s); if(n==1) { PR(L,0); continue; } int i; FOR0(i,L) r[i]=s[i]; r[L]=0; da(r,sa,L+1,130); calHeight(r,sa,L); int low=1,high=L,mid; while(low<=high) { mid=(low+high)>>1; if(ok(mid)) low=mid+1; else high=mid-1; } if(low<=L&&ok(low)) PR(low,pos); else if(high>=1&&ok(high)) PR(high,pos); else puts("none"); }}
