Picture Perfect

Interview

Time limit1sMemory limit128 MB

Summary

For each C, find the factor pair (W, H) with W*H = C closest to a square, and report the smallest perimeter along with W and H.

Level: Easy3 of 10
Topics: Math, Brute force, Number theory, Implementation
Solved: No attempts yet

Problem

Roy has a stack of student yearbook photos. He wants to lay them on a flat surface edge to edge to form a completely filled rectangle whose perimeter is as small as possible. Every photo must be fully visible, and each photo is a square measuring $1 \times 1$ unit.

For example, $12$ photos can be arranged as follows, where each photo is drawn as an X:

XXXX
XXXX
XXXX

They could also be turned the other way:

XXX
XXX
XXX
XXX

Both arrangements are completely filled rectangles with the same perimeter, $14$ units.

For a given number of photos $C$ , find the filled rectangle formed by placing all $C$ photos edge to edge that has the smallest possible perimeter, and report both that perimeter and the rectangle's dimensions.

Input

The input contains several test cases. Each test case is a single positive integer $C$ ( $1 \le C < 65\,000$ ), the number of photos to lay out. The input ends with a line containing $0$ , which must not be processed.

Output

For each value of $C$ , print one line in exactly this format:

Minimum perimeter is P with dimensions W x H

Here $P$ is the smallest possible perimeter, and $W$ and $H$ are the side lengths of the rectangle that achieves it, with $W \le H$ .

Examples1

Example 1

Input

Expected output

Minimum perimeter is 40 with dimensions 10 x 10
Minimum perimeter is 16 with dimensions 3 x 5
Minimum perimeter is 56 with dimensions 13 x 15