## MAXIMUS - Move your armies

Commodus has discovered with your help that the traitor is Maximus. Commodus has gathered N prestigious armies A1 A2 ... AN and asked you to lead them to kill Maximus. A brave warrior like you must now act intelligently to lead the armies to victory.

There are three countries which are considered here,
for simplicity lets name them C_{0}, C_{1}
and C_{2}.
You have moved the armies to C_{0} and you know that
Maximus is in C_{2}.
You are wise enough to know that without all
your N armies you stand no chance against great Maximus. The problem is
that your armies are too egoistic in nature ( after all they were
organized by Commodus ). Only the biggest army can leave any country C_{y}
(Army A_{x} can leave C_{y}, if there is no army A_{i}
in C_{y} with i > x.). Also, the army A_{x}
will go into C_{y} only if it is the biggest army to get there,
i. e. there is no army A_{i} in C_{y} with i > x.

There is another confusion here, all the
armies A_{m} have been trained by a different
commander
and they march differently. Each army A_{m} where m is either 1
or prime can only move
from C_{i} to C_{(i+1)%3}, while your armies A_{m}
where m > 1 is
composite will march only from C_{i} to C_{(i+2)%3}.

Commodus is impatient and he is asking you to find the number of moves you need to reach Maximus. You are planning to reach there with the shortest possible number of moves; tell your answer to Commodus.

Example for N = 2:

The required number of steps would be 7

initially

C0 - A1, A2

C1 -

C2 -

after step 1

C0 - A1

C1 - A2

C2 -

after step 2

C0 - A1

C1 -

C2 - A2

after step 3

C0 -

C1 - A1

C2 - A2

after step 4

C0 - A2

C1 - A1

C2 -

after step 5

C0 - A2

C1 -

C2 - A1

after step 6

C0 -

C1 - A2

C2 - A1

after step 7

C0 -

C1 -

C2 - A1, A2

### Input

The input will consist of at most 100 test cases. Each test case consists of a number N (the number of armies, 1 ≤ N ≤ 5000). The last test case is followed by a line containing 0.

### Output

For each number N, you have to output the number of moves needed to move the
armies to C_{2} with the minimum number of steps.

### Example

Input:1 2 3 4 100 0Output:2 7 21 49 1299510268586153115889930564780511199231

Added by: | Adrian Kuegel |

Date: | 2006-01-29 |

Time limit: | 10s |

Source limit: | 10000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 VB.NET |

Resource: | Codearena 2006 |