## MAXIMUS - Move your armies

no tags

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 C0, C1 and C2. You have moved the armies to C0 and you know that Maximus is in C2. 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 Cy (Army Ax can leave Cy, if there is no army Ai in Cy with i > x.). Also, the army Ax will go into Cy only if it is the biggest army to get there, i. e. there is no army Ai in Cy with i > x.

There is another confusion here, all the armies Am have been trained by a different commander and they march differently. Each army Am where m is either 1 or prime can only move from Ci to C(i+1)%3, while your armies Am where m > 1 is composite will march only from Ci 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 C2 with the minimum number of steps.

### Example

```Input:
1
2
3
4
100
0

Output:
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