Making Rectangles

Time limit1sMemory limit128 MB

Summary

For each N, find the smallest tile count T whose number of unordered factor pairs (a×b rectangles with a≤b) is exactly N.

Level: Medium7 of 10
Topics: Number theory, Brute force, Sorting, Math
Solved: No attempts yet

Problem

Kangsan has a supply of unit square tiles (squares of side length $1$ ), and his favorite shape is a rectangle. He wants to lay tiles out to form a solid rectangle, using every tile with none left over. For a given number of tiles, how many different rectangles can he build? Two rectangles that are rotations of each other count as the same, so an $a \times b$ rectangle is the same as a $b \times a$ rectangle, and a square also counts as a rectangle.

For example, with $6$ tiles he can build two kinds of rectangle, $1 \times 6$ and $2 \times 3$ . With $4$ tiles he can build two kinds, $1 \times 4$ and $2 \times 2$ .

Given $N$ , find the smallest number of unit square tiles for which the number of different rectangles that use all of the tiles is exactly $N$ . For example, when $N = 2$ the answer is $4$ .

Input

The input consists of several test cases, one per line, each a single integer $N$ ( $1 \le N \le 75$ ). The last line contains a single $0$ , which ends the input and is not a test case.

Output

For each test case, output on its own line the smallest number of unit square tiles such that the number of different rectangles using all of the tiles is exactly $N$ (no more and no fewer). The answer never exceeds $10^{18}$ .

Examples2

Example 1
Input
```
2
16
19
0
```
Expected output
```
4
840
786432
```
Example 2
Input
```
1
2
3
4
5
0
```
Expected output
```
1
4
12
24
36
```