Concentration Cards

Time limit1sMemory limit128 MB

Summary

Given N cards of size W by H that can each be rotated, tile a filled rectangle with them and find the smallest possible perimeter.

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

Problem

Stan has a deck of $N$ Concentration Cards. He wants to lay the cards edge-to-edge to form a single, completely filled rectangle whose perimeter is as small as possible. Each card is a rectangle measuring $W$ mm by $H$ mm.

Each card may be rotated by $90^\circ$ , and the cards may be arranged in any way (not necessarily a simple grid) as long as they cover the rectangle exactly, with no gaps and no overlaps.

Figure 1: Concentration Cards

Input

The first line of input contains $C$ , the number of test cases. Each of the following lines contains $N$ , $W$ , and $H$ , each a positive integer not exceeding $1000$ .

Output

For each test case, print on its own line the minimal possible perimeter of the rectangle.

Examples3

Example 1

Input

Expected output

2600
2800
3800

Example 2
Input
```
1
1 1 1
```
Expected output
```
4
```
Example 3
Input
```
1
6 5 5
```
Expected output
```
50
```