Divisors last

#include<bits/stdc++.h>
using namespace std;

#define M 1000000

bool mark[M];

vector<long long>prime;

void sieve()
{
    long long i,j;
        prime.push_back(2);
        for(i=3;i*i<M;i+=2)
        {
            if(mark[i]==false)
            {
                for(j=i*i;j<M;j+=2*i)
                    mark[j]=true;
            }
        }
        for(i=3;i<M;i+=2)
        {
            if(mark[i]==false)
                prime.push_back(i);
        }

}

long long divisors(long long x)
{
    long long div=1,pre=x;
    for(long long j=0;prime[j]<=pre;j++)
    {
        if(x%prime[j]==0)
        {
            long long count=1;
            while(x%prime[j]==0)
            {
                x/=prime[j];
                count++;
            }
            div*=count;
        }
    }

    return div;
}

int main()
{
    sieve();
    long long n,i,k,m;
    scanf("%lld",&n);
    while(n--)
    {
    vector<long long>v;
        long long lower,upper,num=0;
    scanf("%lld %lld",&lower,&upper);
    for(i=lower;i<=upper;i++)
    {
        k=divisors(i);
        if(k>num)
        {
            num=i;
        }
    }

    cout<<num<<endl;
    }

    return 0;

}