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₀, C₁ and C₂. You have moved the armies to C₀ and you know that Maximus is in C₂. 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₂ with the minimum number of steps.

Example

Input:
1
2
3
4
100
0

Output:
2
7
21
49
1299510268586153115889930564780511199231