记录编号	162241	评测结果	AAAAAAAAAA
题目名称	最长数列	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.413 s
提交时间	2015-05-15 17:46:30	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>

#define LL long long
#define ULL long long
#define ipos set<LL>::iterator
#define N 210
#define eps 1e-13

using namespace std;

void file(){
	freopen("series.in","r",stdin);
	freopen("series.out","w",stdout);
}

int n,tot,ans=0;
multiset<LL> T;
multiset<ULL> Tu;
LL a[N];
ULL au[N];
map<LL,int> C;
map<ULL,int> Cu;

int _check1(ULL a1,ULL a2){
	int tmp=2;
	ULL d=a2-a1,now=a2;
	Cu.clear();
	for(int i=1;i<=n;i++) Cu[au[i]]++;
	Cu[now]--;
	while(Cu[now+d]){
		now+=d;
		if(now>0x7fffffff) break;
		Cu[now]--;
		tmp++;
	}
	return 0x7fffffff;
}

int _check2(ULL a1,ULL a2){
	int tmp=2;
	ULL d=a2/a1,now=a2;
	Cu.clear();
	for(int i=1;i<=n;i++) Cu[au[i]]++;
	Cu[now]--;
	while(Cu[now*d]){
		now*=d;
		if(now>0x7fffffff) break;
		Cu[now]--;
		tmp++;
	}
	return 0x7fffffff;
}

ULL _qpow(ULL x,int n){
	ULL ans=1;
	for(;n;n>>=1,x*=x) if(n&1) ans*=x;
	return ans;
}

int _check3(ULL now,int k){
	int tmp=1;
	Cu.clear();
	for(int i=1;i<=n;i++) Cu[au[i]]++;
	Cu[now]--;
	while(Cu[_qpow(now,k)]){
		LL tmp=now;
		now=_qpow(now,k);
		if(tmp>0&&now<tmp) break;
		Cu[now]--;
		tmp++;
	}
	return 0x7fffffff;
}

int check1(LL a1,LL a2){
	int tmp=2;
	LL d=a2-a1,now=a2;
	C.clear();
	for(int i=1;i<=n;i++) C[a[i]]++;
	C[now]--;
	C[a1]--;
	while(C[now+d]){
		now+=d;
		C[now]--;
		tmp++;
	}
	return tmp;
}

int check2(LL a1,LL a2){
	int tmp=2;
	LL d=a2/a1,now=a2;
	C.clear();
	for(int i=1;i<=n;i++) C[a[i]]++;
	C[now]--;
	C[a1]--;
//	if(a1=-a2) cout<<now;
	while(C[now*d]){
		now*=d;
	//	if(a1=-a2) cout<<' '<<now;
		C[now]--;
		tmp++;
	}
//	cout<<endl;
//	if(tmp==3) cout<<"check2 "<<a1<<' '<<a2<<endl;
	return tmp;
}

LL qpow(LL x,int n){
	LL ans=1;
	for(int i=1;i<=n;i++) ans*=x;
//	if(x==-3&&n==3) cout<<"ans = "<<C[ans]<<endl;
	return ans;
}

int check3(LL now,int k){
	int tmp=1;
	C.clear();
	for(int i=1;i<=n;i++) C[a[i]]++;
	C[now]--;
	//if(now==-3&&k==3) cout<<now<<' ';
	while(C[qpow(now,k)]){
		LL temp=now;
		now=qpow(now,k);
		if(temp>0&&now<temp){
			//cout<<"ov\n";
		/*	goto Die;*/break;
		}
	//	if(now==-3&&k==3) cout<<' '<<now;
		C[now]--;
		tmp++;
	}
//	Die:;
//	if(now==-3&&k==3) cout<<endl;
	return tmp;
}

int Te;

int main(){
	file();
	scanf("%d",&Te);
	while(scanf("%d",&n)==1){
		T.clear(); tot=0; ans=0;
		for(int i=1;i<=n;i++){
			LL x;
			scanf("%lld",&x);
			T.insert(x);
		}
		for(ipos i=T.begin();i!=T.end();i++) a[++tot]=(*i);
		n=tot;
		for(int i=1;i<=n;i++) au[i]=(ULL)a[i];
		for(int i=1;i<n;i++){
			for(int j=i+1;j<=n;j++){
				ans=max(ans,min(check1(a[i],a[j]),_check1(au[i],au[j])));
				if(a[i] && a[j]%a[i]==0)
					ans=max(ans,min(check2(a[i],a[j]),_check2(au[i],au[j])));
			}
		}
		for(int i=n;i>=2;i--){
			for(int j=1;j<i;j++){
				ans=max(ans,min(check1(a[i],a[j]),_check1(au[i],au[j])));
				if(a[i] && a[j]%a[i]==0)
					ans=max(ans,min(check2(a[i],a[j]),_check2(au[i],au[j])));
			}
		}
		for(int i=1;i<=n;i++)
			for(int k=0;k<=32;k++){
				ans=max(ans,check3(a[i],k));
			}
		printf("%d\n",ans);
	}
	return 0;
}