Tile Cutting

Youssef is a Moroccan tile installer who specializes in mosaics. He keeps rectangular tiles in many sizes, and every side length is a whole number of centimeters. When he needs a parallelogram tile, he cuts one out of a rectangular tile he already has. His cutting machine projects a one centimeter grid onto the work surface to guide the blade. The limits of the machine, Youssef's taste, and his dislike of wasted tile give the following rules.

• The rectangular tile to be cut goes in the bottom left corner of the work surface, with its four sides on grid lines.
• The blade travels only along a segment joining two different grid points on the boundary of the tile, and the two points must lie on adjacent sides.
• The four corners of the resulting parallelogram lie on the four sides of the rectangle, one corner per side.
• No side of the parallelogram may lie along a side of the rectangle.

Figure 1 shows the eight different ways to cut a parallelogram tile of area 4 square centimeters.

Figure 1: the eight ways to cut a parallelogram of area 4.

Two cuts count as different when the rectangle has a different size or the cut sits in a different place. There is no upper bound on the size of the rectangle Youssef starts from.

Youssef must make tiles of every area from $a_{lo}$ to $a_{hi}$. For which area $a$ in that range can he cut the largest number of different tiles?

The first line contains an integer $n$ ($1 \le n \le 500$), the number of test cases. Each of the next $n$ lines contains two integers $a_{lo}$ and $a_{hi}$ ($1 \le a_{lo} \le a_{hi} \le 500\,000$), the range of areas.

For each test case, print one line with two integers. First print the area $a$ with $a_{lo} \le a \le a_{hi}$ for which the number of ways to cut a parallelogram is largest, then print that number of ways $w$. If several areas reach the largest number, print the smallest of them. No parallelogram has area 1, so the number of ways for $a = 1$ is 0.