GSMATRIX - Matrix

no tags 

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: 2019-01-02 19:28:44

How do I solve this without using brute-force?

:D: 2018-10-20 13:35:24

Also check similar but harder problem YOKOF

nimphy: 2018-04-30 13:13:01

@DIWAKAR BHARDWAJ,but note that each operation just A*B(two);A*B*C(more than two) is invalid.

mahmud2690: 2017-07-10 14:28:19

A big deal :)

makeitdonesolo: 2017-01-26 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: 2016-05-06 22:18:24

Interesting question but input range is too narrow. One line of code in Python.
@Mohamed Badawy: 77 -> 8

Last edit: 2016-05-06 22:31:08
Mohamed Badawy: 2016-01-05 21:48:17

please add more tricky test cases my solution got accepted while it answered wrong to n=77

shally darbari: 2015-12-25 18:52:30

Last edit: 2016-01-03 13:38:22
shally darbari: 2015-12-24 14:30:26

why it is giving wrong answer??any tricky test case??

DIWAKAR BHARDWAJ: 2015-12-23 11:02:49

I think ans should be 4


Added by:jonathanirvings
Date:2015-12-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:ITBPC 2010