1. 
/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Math: Primes
* Problem: 294 - Divisors
* Accepted: 0.308
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {


public static final int MAX = (int)Math.sqrt(1000000000);
public static final boolean[] isPrime = new boolean[MAX+1];
public static final int prime[] = new int[MAX];
public static int maxPrime = 0;
private static int a,b,c,d;

private static void sievePrimes()
{
for(int i = 2; i <= MAX; i++)
isPrime[i] = true;
// sieve the multiples of 2
for(int i = 4; i <= MAX; i+=2)
isPrime[i] = false;

prime[maxPrime++] = 2;

// sieve other numbers
int squareRoot = (int)Math.sqrt(MAX);
for(int i = 3; i <= MAX; i+=2)
if(isPrime[i])
{
prime[maxPrime++] = i;
for(int j = i+i; j <= MAX; j += i)
isPrime[j] = false;
}

/** /
for(int i = 1; i < maxPrime; i++)
System.out.println(prime[i]);
/**/

}

private static int calc(int n)
{
int d = 1, power;
for(int i=0; i < maxPrime; i++)
if(n % prime[i] == 0)
{
//System.out.println(n + " ==> " + prime[i]);
power = 1;
while(n % prime[i] == 0)
{
n /= prime[i];
power++;
//System.out.println(" " + prime[i]);
}
d *= power;
}


if(n != 1)
return d*2;

return d;
}

public static void main(String...args) throws Exception
{
Scanner scanner = new Scanner(System.in);
int caseNumbers = scanner.nextInt();

int n, divisors, max, low, high, save = -1;

sievePrimes();

for(int c=0; c < caseNumbers; c++)
{
low = scanner.nextInt();
high = scanner.nextInt();

max = 0;
for(int i = low; i <= high; i++)
{
divisors = calc(i);
if(divisors > max)
{
save = i;
max = divisors;
}
}

System.out.printf("Between %d and %d, %d has a maximum of %d divisors.\n",
low, high, save, max);
}
}
}