SP729 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

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.

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.