#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <cstring>  
#include <string>  
#include <iomanip>  
#include <vector>  
#include <set>  
#include <algorithm>  
#define MAXN 0x7fffffff  
using namespace std;  
multiset<int> s,t;
int a,b,c,d,l,k1,k2,k3,s1,s2,test;
long long r;
multiset <int>::iterator m,n,x,y,z;
long long ab(long long k)
{
	if (k<0) return -1*k;
		else return k;
}
void suan1(void)
{
	k1=l-d;
	r=l+k1;
	while (1)
	{
		y=t.find(r);
		if (y!=t.end())
		{
			t.erase(r);
			r+=k1;
		}
			else break;
	}
}
void suan2(void)
{
	k2=l/d;
	r=l*k2;
	if (r/2>MAXN) return;
	while (1)
	{
		y=t.find(r);
		if (y!=t.end())
		{
			t.erase(r);
			r*=k2;
		}
			else break;
	}
}
void suan3(void)
{
	int i,j;
	if (r/2>MAXN) return;
	while (1)
	{
		j=r;
		for (i=1;i<k3;i++) r*=j;
		if (r/2>MAXN) break;
		y=t.find(r);
		if (y!=t.end()) t.erase(r);
			else break;
	}
}
int main(void)  
{  
    freopen("series.in","r",stdin);  
    freopen("series.out","w",stdout);  
    scanf("%d",&a); 
	for (b=0;b<a;b++)
	{
		s2=1;
		s.clear();
		scanf("%d",&c);
		for (d=0;d<c;d++) 
		{
			scanf("%d",&l);
			s.insert(l);
		}
		x=s.end();
		x--;
		for (m=s.begin();m!=x;m++)
		{
			for (z=m;;)
			{
				z++;
				if (z==s.end()) break;
				d=*m;
				l=*z;
				if (ab(d)>ab(l))
				{
					test=d;
					d=l;
					l=test;
				}
				for (n=s.begin();n!=s.end();n++) t.insert(*n);
				t.erase(d);
				t.erase(l);
				suan1();
				s1=s.size()-t.size();
				if (s1>s2) s2=s1;
				t.clear();
				if (l%d==0) 
				{
					for (n=s.begin();n!=s.end();n++) t.insert(*n);
					t.erase(d);
					t.erase(l);
					suan2();
					s1=s.size()-t.size();
					if (s1>s2) s2=s1;
					t.clear();
				}
				r=d;
				k3=1;
				while (1)
				{
					if ((r==1)||(r==0)) break;
					if ((r==-1)&&(l==1))
					{
						k3=2;
						break;
					}
					r*=d;
					k3++;
					if (r==l) break;
					if (ab(r)>ab(l)) break;
				}
				if (r==l)
				{
					for (n=s.begin();n!=s.end();n++) t.insert(*n);
					t.erase(d);
					t.erase(l);
					suan3();
					s1=s.size()-t.size();
					if (s1>s2) s2=s1;
					t.clear();
				}
			}
		}
		printf("%d\n",s2);
	}
    fclose(stdin); 
    fclose(stdout);  
    return 0;  
}