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.
Input
The first line consist of a single integer N (1 ≤ N ≤ 120).
Output
In the first line, output the result asked in the problem statement above.
Example Explanation
Here is one of the possible minimum calculation to get A^15.
Matrices that Mr. Dengklek have : A
1st multiplication : A * A = A^2
Matrices that Mr. Dengklek have : A, A^2
2nd multiplication : A*A^2 = A^3
Matrices that Mr. Dengklek have : A, A^2, A^3
3rd multiplication : A^3*A^3 = A^6
Matrices that Mr. Dengklek have : A, A^2, A^3, A^6
4th multiplication : A^6*A^6 = A^12
Matrices that Mr. Dengklek have : A, A^2, A^3, A^6,A^12
5th multiplication : A^12*A^3 = A^15
Example
Input: 15 Output: 5
hide comments
urimaj:
20190102 19:28:44
How do I solve this without using bruteforce? 

:D:
20181020 13:35:24
Also check similar but harder problem YOKOF 

nimphy:
20180430 13:13:01
@DIWAKAR BHARDWAJ，but note that each operation just A*B(two)；A*B*C(more than two) is invalid. 

mahmud2690:
20170710 14:28:19
A big deal :) 

makeitdonesolo:
20170126 07:42:05
Can someone please email their code for this question to me. I've already solved this question but I'm not happy with the way I've solved it. Id(ksuhas19@gmail.com) 

candide:
20160506 22:18:24
Interesting question but input range is too narrow. One line of code in Python.


Mohamed Badawy:
20160105 21:48:17
please add more tricky test cases my solution got accepted while it answered wrong to n=77 

shally darbari:
20151225 18:52:30
Last edit: 20160103 13:38:22 

shally darbari:
20151224 14:30:26
why it is giving wrong answer??any tricky test case?? 

DIWAKAR BHARDWAJ:
20151223 11:02:49
I think ans should be 4 
Added by:  jonathanirvings 
Date:  20151222 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  ITBPC 2010 