Description

You are given 2N cards, numbered as 1, 2, 3, ..., n, n+1, ..., 2n. This is also the initial order of the cards. A shuffle is defined as rearranging the sequence into n+1, 1, n+2, 2, n+3, 3, n+4, 4, ..., 2n, n. It can be proven that for any natural number N, after performing M shuffles, the sequence will return to the initial order for the first time. Write a program to compute the value of M for natural numbers N less than 10,000.

Input Format

A natural number N.

Output Format

The number of shuffles M.

20

20

译文

CodesOnline