SP25977 GSMATRIX - Matrix

Mr. Ganesh, a friend of Mr. Dengklek, give Mr. Dengklek a big matrix A dan asking the result of A^N. Because the matrix A is too big and Mr Dengklek doesn't have a lot of time, he wants to minimize the number of multiplication needed for computing A^N. In this case, assume Mr. Dengklek always stores the matrices that Mr. Dengklek ever computed, thus, if anytime Mr. Dengklek wants to use that matrix again, he can just directly use it without recomputing it. You must help Mr. Dengklek to find out the minimum number of multiplication required to compute A^N.

The first line consist of a single integer N (1

In the first line, output the result asked in the problem statement above.