1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #294 (Divisors)
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=230
*
* @author Andre Wolfram
* @author Christoph Miesel
* @author Robert Seilbeck
* @version 1.0, 03/25/2009
*
* Status : Accepted
* Runtime 0.310
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {

/**
* Findet die Zahl welche höchste Anzahl von Teiler hat aus einen
* Zahlenbereich. Um die Anzahl der Teiler zu bestimmen wird die
* Primfaktorzerlegung verwendet.
*
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));

int lineCount = Integer.parseInt(reader.readLine());
// Schleife über jeden einegebenen Wertebereich
for (int i = 0; i < lineCount; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
int lowerBound = Integer.parseInt(st.nextToken());
int upperBound = Integer.parseInt(st.nextToken());
ArrayList<Integer> prim = new ArrayList<Integer>();

// findet Primzahlen in Wertebereich
int temp = new Double(Math.sqrt(upperBound)).intValue();
for (int num = 2; num <= temp; num++) {
boolean isPrim = true;
int maxDivisor = new Double(Math.sqrt(num)).intValue();
for (int divisor = 2; divisor < maxDivisor; divisor++) {
if (num % divisor == 0) {
isPrim = false;
break;
}
}
if (isPrim) {
prim.add(num);
}
}

int maxDivisorCount = 0;
int number = 0;
for (int val = lowerBound; val <= upperBound; val++) {
HashMap primFaktors = new HashMap();
int tmp = val;
int tmpDivisorCount = 1;
// Primfaktorzerlegung für eine Zahl
for (int n = 0; n < prim.size(); n++) {
if (tmp % prim.get(n) == 0) {
tmp = tmp / prim.get(n);
Object faktor = primFaktors.get(prim.get(n));
if (faktor == null) {
primFaktors.put(prim.get(n), 1);
} else {
primFaktors
.put(prim.get(n), ((Integer) faktor) + 1);
}

if (tmp == 1) {
break;
}
n--;
}
}

// Aus Primfaktoren anzahl Teiler berechnen. Siehe Wikipedia
// Teilerfuntkion
Iterator values = primFaktors.values().iterator();
while (values.hasNext()) {
tmpDivisorCount *= ((Integer) values.next()) + 1;
}
/*
* Primzahlen müssen extra behandelt werden. Da aus Perfomance
* gründen nicht der gesamte Wertebereich nach Primzahlen
* abgesucht wird. Primzahlen haben immer blo� zwei Teiler.
*/
if (val != 1 && tmpDivisorCount == 1) {
tmpDivisorCount = 2;
}
// Vergleich ob Zahl mehr Teiler hat als jede andere bevor.
if (tmpDivisorCount > maxDivisorCount) {
number = val;
maxDivisorCount = tmpDivisorCount;
}
if (tmpDivisorCount == maxDivisorCount) {
number = Math.min(number, val);
}
}
System.out.println("Between " + lowerBound + " and " + upperBound
+ ", " + number + " has a maximum of " + maxDivisorCount
+ " divisors.");
}

}

}