There is a famous piece of music called “Butterfly Lovers” which everyone has heard. Its gentle and soft tune can affect everybody’s mood and hold the breath. In ancient times, girls were not allowed to go to study in schools. A beautiful and talented girl named Yingtai Zhu had to disguise as a boy to study, and she became bosom friends with Shanbo Liang. Liang didn’t knowing that Zhu was a girl, but he admired the clever guys very much and had a good impression on her. Before returning home, Zhu implied to Liang that she would be his wife. Knowing that Zhu was a girl, the delighted Liang hurried to her home, only to find that her family had betrothed her to someone else against her will. Under the pressure of the patriarchal clan rules and feudal ethics, they died for love and return into a pair of butterflies. The moving tragic legend extols pure love and freedom of love.

Once a sunny day in their school and after class, they played a game. Zhu would like Liang to compute integer powers P of numbers quickly and they just kept around two work variables for intermediate results. The first of the two work variables was initialized to the number x for which they were calculating its power (x doesn’t appear in the input), the other was initialized to 1. Liang could only multiply or divide any pair of the work variables and store the result in any work variable, and all operations were in integers, especially division. Liang wanted to prove that he is clever enough to match Zhu. So he would like to solve this problem in minimum number of operations.

Once a sunny day in their school and after class, they played a game. Zhu would like Liang to compute integer powers P of numbers quickly and they just kept around two work variables for intermediate results. The first of the two work variables was initialized to the number x for which they were calculating its power (x doesn’t appear in the input), the other was initialized to 1. Liang could only multiply or divide any pair of the work variables and store the result in any work variable, and all operations were in integers, especially division. Liang wanted to prove that he is clever enough to match Zhu. So he would like to solve this problem in minimum number of operations.

Input contains multiple test cases. The first line contains one integer number P (0 <= P <= 20000).

For each case just output one line with a single integer that is the minimum number of operations it requires to compute the power.

提交代码