学步园

/*
分析：
    2^31-1很大，不过sqrt后就不大了。

                                 2012-11-12
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
struct A
{
	int num;
	char name[50];
}E[1011];
int num[70001];
int cmp(const void *a,const void *b)
{
	struct A *c,*d;
	c=(struct A *)a;
	d=(struct A *)b;
	return strcmp(c->name,d->name);
}
void getprime()
{
	int i,l;
	memset(num,-1,sizeof(num));
	num[0]=num[1]=0;
	for(i=2;i<=70000;i++)
	{
		if(num[i])
		{
			for(l=2*i;l<=70000;l+=i)
			{
				num[l]=0;
			}
		}
	}
}
int main()
{
	int T;
	int n;
	int i,l;
	int t,pre;
	int temp,base,ans;

	getprime();

	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)	scanf("%s%d",E[i].name,&E[i].num);
		qsort(E,n,sizeof(E[0]),cmp);

		ans=-1;
		base=-1;
		for(i=0;i<n;i++)
		{
			t=(int)sqrt((double)E[i].num);
			temp=0;
			pre=-1;
			for(l=2;l<=t;l++)
			{
				if(E[i].num%l==0)
				{
					if(l!=pre && num[l])	{temp++;pre=l;}
					E[i].num/=l;
					t=(int)sqrt((double)E[i].num);
					l--;
				}
			}
			if(E[i].num>1 && E[i].num!=pre)	temp++;
			if(temp>base)	{base=temp;ans=i;}
		}

		printf("%s\n",E[ans].name);
	}
	return 0;
}