Humanity's Last Code Exam / 2015_J / Tile Cutting

question title

Tile Cutting

question content

## Problem Statement

Youssef is a Moroccan tile installer who specializes in mosaics. He has rectangular tiles of various dimensions, all measured in integer centimeters. When Youssef needs parallelogram-shaped tiles, he cuts them from his existing supply. To facilitate this, he invented a tile cutting machine that uses a centimeter grid to guide the cuts. The cutting process is governed by these rules:

1. The rectangular tile must be positioned in the bottom left corner of the cutting surface, aligned with the grid lines.
2. The cutting blade can cut along any line connecting two different grid points on the tile boundary, provided the points are on adjacent boundary edges.
3. The four corners of the resulting parallelogram tile must lie on the four sides of the original rectangular tile.
4. No edge of the parallelogram tile can coincide with an edge of the rectangular tile.

Figure J.1 illustrates the eight different ways to cut a parallelogram tile of area 4 square centimeters from a rectangular tile, adhering to these restrictions.

Youssef needs to cut tiles of every area between `alo` and `ahi`. He wants to know, for which area `a` in this range, can he cut the maximum number of different tiles?

### Input

The input consists of multiple test cases:

- The first line contains an integer `n` (1 ≤ n ≤ 500), the number of test cases.
- The next `n` lines each contain two integers `alo`, `ahi` (1 ≤ alo ≤ ahi ≤ 500,000), representing the range of areas of the tiles.

### Output

For each test case `alo`, `ahi`, output the value `a` between `alo` and `ahi` such that the number of possible ways to cut a parallelogram of area `a` is maximized, along with the number of different ways `w` to cut such a parallelogram. If there are multiple possible values of `a`, display the smallest one.

### Sample Input

Code

2
4 4
2 6

### Sample Output

Code

4 8
6 20

platform

atcoder