Container

Time limit1sMemory limit128 MB

Summary

Given n containers stackable 5-high, find the rectangular grid of stacks (with fixed spacing rules) minimizing area then minimizing the length-width gap.

Level: Medium5 of 10
Topics: Math, Brute force, Implementation
Solved: No attempts yet

Problem

Sanggeun runs a harbor and wants to build a lot to store container boxes.

The harbor sits on muddy ground, so laying a solid foundation is very expensive. He therefore does not want to make the lot any larger than necessary.

Each container is 40 meters long and 8 meters wide. Containers may be stacked on top of one another, up to 5 per position. Every container must be placed in the same orientation.

The container stacks (the containers piled at one position) are arranged in a rectangular grid. Along the length (40 m) direction, 4 meters of empty space is required between neighboring stacks; along the width (8 m) direction, 2 meters is required between neighboring lines. The same clearance applies at the outer boundary of the lot: there must be 4 meters of margin at each end along the length direction and 2 meters at each end along the width direction.

The lot must be rectangular. Given the number of containers $n$ to store, find the best lot size. First, the area must be as small as possible; among lots of equal area, it should be as close to a square as possible.

For example, the best lot for placing 8 stacks is 92 × 42 = 3864.

Input

The first line contains the number of test cases (at most 100). Each test case is a single line containing $n$ , the number of containers to store. $n$ is a positive integer not greater than $10^{12}$ .

Output

For each test case, print the length, the width, and the area of the best lot on one line. The length must be greater than or equal to the width, in the format LENGTH X WIDTH = AREA. If several lots are possible, print the one with the smallest area; if several have the same smallest area, print the one whose (length − width) is smallest.

Examples3

Example 1

Input

Expected output

48 X 12 = 576
48 X 32 = 1536
52 X 48 = 2496
92 X 32 = 2944
92 X 42 = 3864
136 X 32 = 4352

Example 2
Input
```
1
1
```
Expected output
```
48 X 12 = 576
```
Example 3
Input
```
1
5
```
Expected output
```
48 X 12 = 576
```