The worker of the department of the technical control liked to make with rejects the “dominoes” which have identical values. The enterprise which produced K-dominoes did not know it. It got always claims acted on the sum which equaled to the cost of the K-“dominoes”.

The cost of K-“dominoes” was equal to the quantity of the “dominoes” in the set which buyer bought. The worker of the DTC made with rejects not only the “dominoes” which have identical values and some more but not more than half then the quantity of the “dominoes” which he exactly made with rejects because he did not want to be laid off. You have to indicate which set of the K-dominoes buyer bought. You know the sum of claim which got the enterprise.

Input

A one number S is a sum of claim, which the enterprise got, S ≤ 2000000000.

Output

A one number is an index K of the K-“dominoes” which buyer bought.