You want to decorate your floor with square tiles. You like rectangles. With six square flooring tiles, you can form exactly two unique rectangles that use all of the tiles: 1×6, and 2×3 (6×1 is considered the same as 1x6. Likewise, 3×2 is the same as 2×3). You can also form exactly two unique rectangles with four square tiles, using all of the tiles: 1×4, and 2×2.
Given an integer N, what is the smallest number of square tiles needed to be able to make exactly N unique rectangles, and no more, using all of the tiles? If N=2, the answer is 4.
There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (1 ≤ N ≤ 75), which represents the number of desired rectangles. The input will end with a line with a single 0.
For each test case, output a single integer on its own line, representing the smallest number of square flooring tiles needed to be able to form exactly N rectangles, and no more, using all of the tiles. The answer is guaranteed to be at most 10^18. Output no extra spaces, and do not separate answers with blank lines.