61 lines
1.4 KiB
C++
61 lines
1.4 KiB
C++
#include <iostream>
|
|
#include <cstdio>
|
|
#include <cmath>
|
|
using namespace std;
|
|
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
|
|
int cnt[100]={19,0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,2,1,2,1,2,1,3,1,1,2,2,2,2,1,2,2
|
|
,2,1,3,1,2,2,2,1,2,1,2,2,2,1,2,2,2,2,2,1,3,1,2,2,1};
|
|
long long considrt[6000000],nconsidrt;
|
|
void GetConsider(int r)
|
|
{
|
|
nconsidrt=0;
|
|
int i,j,sz;
|
|
for(i=0;prime[i]<=r;i++)
|
|
{
|
|
sz=nconsidrt;
|
|
for(j=0;j<sz;j++)
|
|
{
|
|
if(considrt[j]*prime[i]<=63)
|
|
considrt[nconsidrt++]=considrt[j]*prime[i];
|
|
}
|
|
considrt[nconsidrt++]=prime[i];
|
|
}
|
|
}
|
|
long long cal(long long x)
|
|
{
|
|
long long ret(0);
|
|
for(int i=0;i<nconsidrt;i++)
|
|
{
|
|
if(cnt[considrt[i]]&1)
|
|
ret+=(long long)pow(x+0.5,1.0/considrt[i])-1;
|
|
else
|
|
ret-=(long long)pow(x+0.5,1.0/considrt[i])-1;
|
|
}
|
|
return x-ret-1;
|
|
}
|
|
long long solve(long long n,int r)
|
|
{
|
|
GetConsider(r);
|
|
long long ans = n;
|
|
while(1)
|
|
{
|
|
long long temp = cal(ans);
|
|
if(temp == n)
|
|
break;
|
|
ans += n - temp;
|
|
}
|
|
return ans;
|
|
}
|
|
int main()
|
|
{
|
|
int ncase,r;
|
|
long long n;
|
|
scanf("%d",&ncase);
|
|
while(ncase--)
|
|
{
|
|
scanf("%I64d%d",&n,&r);
|
|
printf("%I64d\n",solve(n,r));
|
|
}
|
|
return 0;
|
|
}
|