题目内容

在数字合成游戏中，你的初始数值为 $1$。每一次操作，你可以选择一个合成因子 $w$（$w \ge 2$）并将当前数值乘上 $w$。然而，游戏禁止使用任何整数的平方作为合成因子，即不存在整数 $y$ 使得 $w = y \times y$。操作顺序不同的序列被视为不同的方案。现在给定目标数值 $n$，请你计算从 $1$ 合成到 $n$ 一共有多少种不同的操作序列。整数 $n$ 满足 $1 \le n \le 2 \times 10^5$。

输入描述

输入共一行，包含一个整数 $n$。

输出描述

输出一个整数，表示满足条件的操作序列总数。

样例1

输入

1

输出

1

说明

初始数值为 1，已经等于目标 1，不需要任何操作。空操作序列也算一种方案，因此答案为 1。

样例2

输入

6

输出

2

说明

从 1 合成到 6，合法的合成因子不能是完全平方数（即不能是 1, 4, 9, ...）。 允许的因子序列有两种：

• $1 \to 2 \to 6$（因子依次为 2, 3）
• $1 \to 3 \to 6$（因子依次为 3, 2） 因此共有 2 种操作序列，答案为 2。

样例3

输入

12

输出

5

说明

目标为 12。所有合法的操作序列对应的因子序列（每个因子 $\ge 2$ 且不是完全平方数）为：

• $[12]$：一步合成 $1 \times 12 = 12$
• $[2, 6]$：$1 \times 2 = 2$，$2 \times 6 = 12$
• $[6, 2]$：$1 \times 6 = 6$，$6 \times 2 = 12$
• $[2, 2, 3]$：$1 \to 2 \to 4 \to 12$（中间值 4 不是合成因子，因子均为 2, 2, 3，均非平方数，因此合法）
• $[2, 3, 2]$
• $[3, 2, 2]$

其中 [4,3] 不合法，因为 4 是完全平方数，不能作为合成因子。所有合法有序排列共计 5 种，故答案为 5。