简单递归

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

请模拟以下的函数

n为正整数。

当n为奇数时,f(n)=1;

当n为偶数时,f(n)=f( ⌊n^0.5⌋ )+f(n/2)。

 

注:n^0.5即为n的算术平方根, ⌊⌋ 为向下取整符号, ⌊1⌋= ⌊1.1⌋= ⌊1.5⌋= ⌊1.9⌋=1, ⌊2.00000⌋=2    

Input

多组输入,输入到EOF结束,每行输入一个正整数n。

Output

对于每组输入,输出一个整数f(n)。

Sample Input

12

Sample Output

4

Hint

Source

【2017级《程序设计基础(B)II》期末上机考试补测】玄黄