Problem Description

There is a variable $ X $ with an initial value of $ 1 $.

Takahashi performed the operation "triple $ X $" thirty times. However, instead of resulting in $ 3^{30} $, $ X $ ended up being $ N $.

Aoki, who loves pranks, confessed to the following action:

• He chose an integer $ k $ such that $1 \leq k \leq 30$ and added $ 1 $ to the variable $ X $ immediately after Takahashi's $ k $-th operation.

Given $ N $, find $ k $. If no such $ k $ exists such that the operation results in $ N $, output $ -1 $.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the answer. If no such $ k $ exists such that the operation results in $ N $, output $ -1 $.

Sample Input and Output

Sample Input #1

205894618879050

Sample Output #1

10

Sample Input #2

314159265358979

Sample Output #2

-1

Notes/Hints

Constraints

• $1 \leq N \leq 10^{15}$
• $N \neq 3^{30}$
• All inputs are integers.

Sample Explanation 1

The behavior for $ k=10 $ is shown. Tripling $ 1 $ ten times results in $ 59049 $. Due to Aoki's prank, $ 1 $ is added, resulting in $ 59050 $. Further tripling it twenty times results in $ 205894618879050 $.

见题面 Input 部分

见题面 Output 部分