UVA - 294

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

using namespace std;

#define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define RFOR(i,a,b) for(__typeof(b) i=(a); i>(b); i--)
#define RESET(t,value) memset((t), value, sizeof(t))
typedef long long int64;
typedef long double d64;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define PI acos(-1.0)
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define pii pair<double,double>
#define G struct node

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

int GCD(int a, int b){return (b == 0 ? a : GCD(b, a % b));}
int LCM(int a, int b){ return (a * (b/ GCD(a, b))); }
int ABS(int a) {return ((a >= 0) ? a : -a); }

vector < int > pset;
void initSet(int _size){ pset.resize(_size); FOR(i,0,_size-1) pset[i]=i;}
int findSet(int i){return (pset[i]== i)?i: (pset[i] = findSet(pset[i]));}
void unionSet(int i,int j){ pset[findSet(i)]=findSet(j);}
bool isSameSet(int i,int j){ return findSet(i)==findSet(j);}

#define Max 10010
long long status[(Max/32)+2];
vector <long long> primeList;
map <long long, long long> primeFactor;

bool Check(long long N,long long pos){return (bool)(N & (1<<pos));}
int Set(long long N,long long pos){ return N=N | (1<<pos);}

void RSieve(long long N)
{
     primeList.clear();
     long long i, j, sqrtN;
     sqrtN = long( sqrt( N ) );
     for( i = 3; i <= sqrtN; i += 2 )
     {
         if( Check(status[i>>5],i&31)==0)
         {
             for( j = i*i; j <= N; j += (i<<1) )
             {
                 status[j>>5]=Set(status[j>>5],j & 31)   ;
             }
         }
     }
     primeList.pb(2);
     for(i=3;i<=N;i+=2)
         if( Check(status[i>>5],i&31)== 0) primeList.pb(i);
}

long long d(long long n){
    primeFactor.clear();
        REP(i, primeList.size()){
            long long p = primeList[i];
            while(n % p == 0){
                n = n / p;
                primeFactor[p] += 1;
            }
        }

    long long result = 1;
    REP(i, primeFactor.size()){
        long long r = primeFactor[i];
        result *= (r + 1);
    }
    return result;
}

int main()
{
    READ("input.txt");
    int t;
    RSieve(10010); //কেন কাজ করবে ? বাল :/
    long long u,l;
    cin>>t;
    while(t--)
    {
        cin>>l>>u;
        long long max = -1, n;
        FOR(i,l,u) {
            if(d(i)>max) {
                max = d(i);
                n = i;
            }
        }
        cout<<"Between "<<l<<" and "<<u<<", "<<n<<" has a maximum of "<<max<<" divisors.\n";
    }
    return 0;
}