On the planet Farale, aliens with B arms walk around. The researcher Mitofey is meticulously studying their language and number system. As you may have guessed, all numbers on Farale are written in base B. Despite this, even the Faralians understand the value of the binary number system, because not so long ago the first computer on their planet was built! Yes, it is still bulky, but it can add numbers! And not just in any way, but using bitwise exclusive OR! That is exactly what the manual says!

Unfortunately, Mitofey has not yet fully figured out the Faralian language. Therefore, when he was leafing through the manual and found the function συναριθμo(x), he translated its description as follows: “συναριθμo(x) — means the sum of the sum of digits and the bitwise exclusive OR of the digits. For example, in the decimal system συναριθμo(12₁₀) = (1 + 2) + (1 ⊕ 2) = 6₁₀, συναριθμo(26₁₀) = (2 + 6) + (2 ⊕ 6) = 12₁₀, and in the ternary system συναριθμo(202₃) = (2 + 0 + 2) + (2 ⊕ 0 ⊕ 2) = 11₃”. Mitofey added the examples himself, since he was forbidden to touch the computer.

It is not hard to see that συναριθμo(x) takes any positive integer in base B and returns a positive integer in base B. Mitofey became interested in one question: what happens if we substitute the result of the function back into the function? And then again, and again, and so on forever? It is clear that for some numbers, at some point, we will obtain a result that we have already seen before. In other words, we have entered a cycle. Let the length of the cycle containing x be the minimum positive integer k such that συναριθμo^k(x) = x. Find the length of the largest cycle.

The only line contains an integer B — the base of the number system on the planet Farale (3 ≤ B ≤ 10¹²).

Print the length of the largest cycle of the function συναριθμo(x).