题目描述

农夫约翰正在扩增牛群．通过调整饲料的量，他可以控制牛群中每头母牛所生的小牛的数量．如果他给每头奶牛喂了相同量的饲料，她们就产下了相同数量的牛犊．

开始，他喂了一头母牛，希望通过若干代的饲育得到$\red{N}$只奶牛．假如$\red{N= 12，}$那么约翰应该喂那只最初的奶牛足够的饲料，使其生$\red{3}$只牛犊．第二代牛长大后，他就给她们喂足够的饲料，使它们生下$\red{4}$只牛犊，从而最后一代中有$\red{12}$只牛了．

牛一旦生产，约翰就把她卖了．所以，农场里只保留最新一代的牛． 每头牛生牛犊的数量不少于$\red{2，}$且无上限．约翰可以通过多少种不同的方式使最络牛的总数为$\red{N(1≤}$$\red{N≤}$$\red{2\times 10^9)}$方法的总数量不超过$\red{2\times 10^9.}$

输入格式

整数$\red{N.}$

输出格式

获得$\red{N}$头牛的方式总数．

样例

输入样例

12

输出样例

8

提示

样例说明

获得$\red{12}$头牛的方法是$\red{(2，}$$\red{2，}$$\red{3).}$即，第一二代都生产$\red{2}$头，第三代生产$\red{3}$头（一共$\red{12}$头）．

其余$\red{7}$种方法为$\red{(2，}$$\red{3，}$$\red{2)，}$$\red{(3，}$$\red{2，}$$\red{2)，}$$\red{(3，}$$\red{4)，}$$\red{(4，}$$\red{3)，}$$\red{(12)，}$$\red{(2，}$$\red{6)，}$$\red{(6，}$$\red{2).}$