拆分后的叶子数

难度：T2

【知识点：记忆化搜索】

前置知识：函数、递归、数组、完整状态与无环依赖。

题目描述

一块初始能量为 $N$。能量 $x<2$ 的块停止拆分，算一片叶子；能量 $x\ge2$ 的块必须拆成 $\lfloor x/2\rfloor,\lfloor x/3\rfloor$ 两块，分别继续。即使能量相同也仍是两块。求最终叶子总数；能量为 $0$ 的终止块也算一片。

规则说明

符号 $\lfloor x\rfloor$ 表示向下取整，即取不大于 $x$ 的最大整数。例如 $\lfloor 7/2\rfloor=3$，$\lfloor 6/2\rfloor=3$。

输入格式

一行一个整数 $N$。

输出格式

一行叶子总数。

样例输入

6

样例输出

4

样例解释

$6$ 拆成 $3,2$；$3$ 拆成 $1,1$，$2$ 拆成 $1,0$，最终共 $4$ 片。

数据范围

$0\le N\le10^6$。