The Archaeologist's Trouble III

Time Limit: 1 Second    Memory Limit: 32768 KB

Mr. Genius appreciated your work very much, but now he has a hard nut to crack. Several days ago, someone sent him a stone chest carved with beautiful graphics. Being a excellent archaeologist, Lazy knew that the chest must have some secret.

When he managed to open the chest, he is pleasantly surprised to find it a ACM (Auto Clock Machine). After some study on the machine, he finally followed how the clock worked.

The Principle of the operation of the clock.

The clock had N stone balls. These balls initially were placed in a queue.

Every minute the ball at the head of the queque rolled into the minute stack.

The Minute stack could hold 9 balls. When the 10th ball came, it make the stack clear up. The 10th ball rolled into the 10-minute stack. The first 9 balls in the stack rolled into the queue in reverse order.

The 10-minute stack could hold 5 balls. When the 6th ball came, it make the 10-minute stack clear up. The 6th ball rolled into the hour stack. The 5 balls in the stack rolled into the queue in reverse order.

The hour stack could hold 23 balls. When the 24th ball came, it make the hour stack clear up. The 23 balls in the stack rolled into the queue in reverse order, then the 24th ball rolled into the queue.

When we checked the number of stones at those stack, we got the time.

After 24 hours, all the stone balls returned the queue. Obviously, the order of queue is different from the one 24 hours before. However, several months later, Mr. Genius found that the balls return the initial order. He called this time interval as "Clock Period". Mr. Genius knew the period was not only one. If 10 days is a "Clock Period", so is 20 days. He wanted to find the minimum one, "T". But Mr. Genius had no time to do experiments. Then he turned to you, a gifted programming student, believing that you could help him.

You task is to find out T according to a given N.

Input

The input contains several test cases.

Each case contain a positive integer, N (38 <= N <= 400), which is the number of the balls in the clock.

Zero terminates the input.

Output

For each case, ouput in one line the minimum clock period T, for the corresponding N.

Sample Input

38 
49
50
0

Sample Output

1870
30
138

Submit

Source: ZOJ Monthly, January 2004