n以内约数最多的数

题意非常简单，问 [1, n] 范围内约数最多的数是几。

Input

输入第一行为数据组数 T （ T <= 100 ）。

对于每组数据，只有一个数字 n （ 1 <= n <= 10⁹ ）

Output

对于每组数据，请在一行中输出两个数，即 [1, n] 范围中约数最多的那个数（如果有多个，则输出最小的那个），以及其约数的个数，用一个空格隔开。

Sample Input

3

10

20

30

Sample Output

6 4

12 6

24 8

详见：

及连接里面的连接，里面的连接，……

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ll long long
int prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};  
ll n,res2,res1;//res1 数      res2  约数个数

void dfs(int now,int last,ll ans,ll y_ans)//now  当前prime数组的下标，
{                                         //last （now-1）质因子的个数
	int i;                                //ans   当前的数
	if(now==15) return ;                  //y_ans  当前数的约数的个数
	if(y_ans>res2 || (y_ans==res2&&ans<res1)) res1=ans,res2=y_ans;
	for(i=1,ans*=prime[now];i<=last&&ans<=n;i++,ans*=prime[now])
		dfs(now+1,i,ans,y_ans*(i+1));
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		res1=res2=1;
		scanf("%lld",&n);
		dfs(0,32,1,1);
		printf("%lld %lld\n",res1,res2);
	}
}