약수 개수의 최댓값

시간 제한2초메모리 제한512 MB

요약

길이가 1001 이하인 구간 10개 이하가 주어질 때, 각 구간 [L, U]에서 약수가 가장 많은 수의 약수 개수를 구한다.

문제

정수 구간 $[L, U]$ 에 속하는 모든 정수의 약수 개수를 세고, 그중 가장 큰 값을 구한다. 양 끝 값 $L$ 과 $U$ 도 구간에 포함한다. 약수를 셀 때는 1과 자기 자신도 함께 센다.

첫 줄에 처리할 구간의 개수 $C$ 가 주어진다.

이어지는 $C$ 개의 줄에는 각각 구간의 두 끝값 $L$ 과 $U$ 가 공백으로 구분되어 주어진다.

제약 조건

각 구간마다 한 줄씩, 그 구간에서 나온 가장 큰 약수 개수를 출력한다.

예제 1

입력

5
1 10
1000 1000
9999900 10000000
35 999
25 25

예상 출력