Perfect Cubes

Time limit1sMemory limit128 MB

Summary

Find all quadruples a, b, c, d with 2 <= a <= N, b < c < d, and a^3 = b^3 + c^3 + d^3, printed in sorted order.

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

Problem

Fermat's Last Theorem states that when $a$ , $b$ , $c$ are non-zero integers and $n$ is a natural number greater than 2, there are no natural numbers $a$ , $b$ , $c$ satisfying $a^n = b^n + c^n$ .

However, it is not hard to find natural numbers greater than 1 that satisfy the perfect-cube equation $a^3 = b^3 + c^3 + d^3$ . For example, $12^3 = 6^3 + 8^3 + 10^3$ .

Given an integer $N$ , write a program that finds every quadruple $\{a, b, c, d\}$ satisfying this perfect-cube equation with $2 \le a \le N$ . Here $b$ , $c$ , and $d$ are all greater than 1 and satisfy $b < c < d$ .

Input

The first line contains an integer $N$ ( $2 \le N \le 100$ ).

Output

Print each solution on its own line in increasing order of $a$ ; for the same $a$ , order by increasing $b$ , then $c$ , then $d$ . Each line has the form:

Cube = a, Triple = (b,c,d)

If no quadruple satisfies the conditions, print nothing.

Hint

Fermat's Last Theorem was proved by Andrew Wiles in 1995.

Examples4

Example 1

Input

Expected output

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

Example 2
Input
```
6
```
Expected output
```
Cube = 6, Triple = (3,4,5)
```

Example 3

Input

Expected output

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)

Example 4
Input
```
5
```
Expected output