타일 자르기

Youssef은 모자이크를 전문으로 하는 모로코의 타일 시공자다. 가지고 있는 직사각형 타일은 크기가 다양하고, 모든 변의 길이는 센티미터 단위의 정수다. 평행사변형 모양의 타일이 필요하면 손에 있는 직사각형 타일에서 잘라 낸다. 재단기는 작업면에 1센티미터 격자를 비춰서 칼날의 위치를 잡아 준다. 기계의 한계, Youssef의 취향, 타일을 버리기 싫어하는 성격 때문에 자르는 방법에는 다음 규칙이 있다.

• 자를 직사각형 타일은 작업면의 왼쪽 아래 구석에 놓고, 네 변을 격자선에 맞춘다.
• 칼날은 타일 경계 위의 서로 다른 두 격자점을 잇는 선분을 따라서만 지나가며, 두 점은 서로 이웃한 변 위에 있어야 한다.
• 잘라 낸 평행사변형의 네 꼭짓점은 직사각형의 네 변에 하나씩 놓인다.
• 평행사변형의 어떤 변도 직사각형의 변 위에 놓일 수 없다.

그림 1은 넓이가 4제곱센티미터인 평행사변형 타일을 잘라 내는 서로 다른 8가지 방법이다.

그림 1: 넓이가 4인 평행사변형을 잘라 내는 8가지 방법.

직사각형의 크기가 다르거나 자르는 위치가 다르면 서로 다른 방법으로 센다. 재료로 쓰는 직사각형의 크기에는 상한이 없다.

Youssef은 넓이가 $a_{lo}$ 이상 $a_{hi}$ 이하인 타일을 모두 만들어야 한다. 이 범위의 넓이 $a$ 중에서 서로 다른 타일을 가장 많이 잘라 낼 수 있는 것은 무엇인가?

첫 줄에 테스트 케이스의 수 $n$ ($1 \le n \le 500$)이 주어진다. 이어지는 $n$개의 줄에는 각각 두 정수 $a_{lo}$, $a_{hi}$ ($1 \le a_{lo} \le a_{hi} \le 500\,000$)가 주어지며, 넓이의 범위를 뜻한다.

각 테스트 케이스마다 한 줄에 정수 두 개를 출력한다. 먼저 $a_{lo} \le a \le a_{hi}$인 넓이 $a$ 중 평행사변형을 잘라 내는 방법의 수가 가장 많은 $a$를 출력하고, 이어서 그 방법의 수 $w$를 출력한다. 방법의 수가 최대인 $a$가 여럿이면 그중 가장 작은 것을 출력한다. 넓이가 1인 평행사변형은 만들 수 없으므로 $a = 1$의 방법의 수는 0이다.