解题思路

把问题看成：求$n$的所有有序因子分解数量，且分解中的每一项都 不是完全平方数。

设$dp[x]$表示把$x$分成若干份后，满足条件的方案数。

对于任意一个合法方案，第一份可以取某个因子$d$，要求：

• $d \mid x$

题目内容

小红生日快到了，他准备了$n$份愉悦值打算分给同学。为此，他需要把$n$份愉悦值恰好分成$m$份（$m$为任意正整数），每份的大小为$a_i$($a_i$为正整数），且使得$\prod^{m}_{i=1}a_i=a_1×a_2×···×a_m=n$。由于小红不喜欢完全平方数，所以他不会使得任意一份愉悦值是一个完全平方数。

注意，分的顺序重要，即$a×b×c和a×c×b$被视为两种方案。

请计算并输出所以满足条件的方案数量。

一个数$s$如果存在一个整数$y$使得$y*y=x$,那么$x$可以叫做完全平方数。

输入描述

在一行上输入一个整数$n(1≤n≤2×10^5)$,表示愉悦值的的数量。

输出描述

在一行输出一个整数，表示愉悦值分配的方案数量。

样例1

输入

12

输出

6

说明

​ 具体的方案为：

$[2,2,3][2,3,2][3,2,2],[2,6][6,2][12]$共$6$种。